专栏首页大白技术控的技术自留地滴滴2016.09.06校招 在线笔试 - 2道编程题

滴滴2016.09.06校招 在线笔试 - 2道编程题

滴滴2016.09.06校招 在线笔试 - 2道编程题

1、连续子数组的最大和

题目描述

一个数组有N个元素,求连续子数组的最大和。例如:[-1,2,1],和最大的连续子数组为[2,1],其和为3。

输入描述
输入为两行。
第一行一个整数n (1 <= n <= 100000), 表示一共有n个元素,第二行为n个数,每个元素每个整数都在32位int范围内。以空格分隔。
输出描述
所有连续子数组中和最大的值。
输入例子
3
-1 2 1
输出例子
3

分析:

参考解答:

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    int n;
    scanf("%d",&n);
    int sum = 0, mx = -99999999;    // 初值的选取需注意, 不能取INT_MIN
    for(int j = 0; j < n; j++){
        int temp;
        scanf("%d",&temp);
        if(sum < 0) sum = temp;
        else sum += temp;
        mx = max(sum, mx);
    }
    printf("%d\n",mx);
}

2、餐馆

题目描述

某餐馆有n张桌子,每张桌子有一个参数:a可容纳的最大人数;有m批客人,每批客人有两个参数:b人数、c预计消费金额。在不允许拼桌的情况下,请实现一个算法选择其中一部分客人,使得总预计消费金额最大。

输入描述
输入包括m+2行。
第一行包括2个整数n(1<=n<=50000),m(1<=m<=50000);
第二行为n个参数a,即每个桌子可容纳的最大人数,以空格分隔,范围均在32位int范围内;
接下来m行,每行两个参数b和c,分别表示第i批客人的人数和预计消费金额,以空格分隔,范围均在32位int范围内。
输出描述
输出一个整数,表示最大的总预计消费金额。
输入例子
3 5
2 4 2
1 3
3 5
3 7
5 9
1 10
输出例子
20

分析:

贪心法。先把顾客进行消费金额降序,人数升序排序。 然后枚举每波顾客去二分当前最适合的 桌子的容量,维护答案即可,注意答案可能爆int。这题裸暴力过不了。不能拆桌。时间复杂度:O(mlogm + nlogm)

注意: 结果需要使用long long(相应printf的格式控制为%lld), 如果忘了用long long, 样例只会通过50%!

参考code:

#include <iostream>
#include <map>
#include <vector>
#include <map>

using namespace std;

struct node{
    int b,c;
};
int comp(node x, node y){
    if (x.c == y.c) {
        return x.b < y.b;
    } 
    return x.c > y.c;  
}
int n,m;
long long ans;
std::vector<node> v;
std::multimap<int, int> mp;
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 0; i < n; i++){
        int x; scanf("%d",&x);
        mp.insert(std::pair<int, int>(x, 1));
    }
    for(int i = 0; i < m; i++){
        int x, y;
        scanf("%d%d",&x,&y);
        node tmp;
        tmp.b = x, tmp.c = y;
        v.push_back(tmp);
    }
    sort(v.begin(),v.end(),comp);
    for(int i = 0; i < m; i++){
        std::map<int,int>::iterator it = mp.lower_bound(v[i].b);
        if (it != mp.end()) {
            mp.erase(it);
            ans += v[i].c;
        }
    }
    printf("%lld\n",ans);
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C#版 - PAT乙级(Basic Level)真题 之 1013.数素数_牛客网

    在线提交: https://www.nowcoder.com/pat/6/problem/4079 或 PTA(拼题A,原PAT) https://...

    Enjoy233
  • C++版 - 剑指offer面试题38:数字在已排序数组中出现的次数

    提交网址: http://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2?tpId=13&...

    Enjoy233
  • C++版 - 剑指offer 面试题30:最小的K个数(topK问题) 题解

    题目: 输入n个整数,找出其中最小的k个数。例如:例如输入4 、5 、1、6、2、7、3 、8 这8 个数字,则最小的4 个数字是1 、2、3 、4

    Enjoy233
  • 有序数组中与任意数组查找不同的部分-二分查找

    sr
  • hdu1017

    @坤的
  • 【每日算法Day 63】LeetCode 第 179 场周赛题解

    https://leetcode-cn.com/problems/generate-a-string-with-characters-that-have-odd...

    godweiyang
  • 每日算法系列【EOJ 3031】二进制倒置

    给定一个整数 、将 的 334 位二进制表示形式(不包括开头可能的值为 0 的位, 表示为 1 位 0)前后倒置,输出倒置后的二进制数对应的整数。

    godweiyang
  • LeetCode Contest 180

    ShenduCC
  • 河北工业大学ACM选拔赛10月末

    给树染色.相邻结点的颜色不同.求最后的颜色.后面的颜色会覆盖前面的.没有染色成功的输出0

    xiaohejun
  • 一遍记住 8 种排序算法与 Java 代码实现

    (如果每次比较都交换,那么就是交换排序;如果每次比较完一个循环再交换,就是简单选择排序。)

    挨踢小子部落阁

扫码关注云+社区

领取腾讯云代金券