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

1、连续子数组的最大和

题目描述

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

输入描述

输入为两行。
第一行一个整数n (1 <= n <= 100000), 表示一共有n个元素，第二行为n个数，每个元素每个整数都在32位int范围内。以空格分隔。

输出描述

所有连续子数组中和最大的值。

输入例子

3
-1 2 1

输出例子

分析:

参考解答:

#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范围内。

输出描述

输出一个整数，表示最大的总预计消费金额。

输入例子

输出例子

分析:

贪心法。先把顾客进行消费金额降序,人数升序排序。然后枚举每波顾客去二分当前最适合的桌子的容量，维护答案即可,注意答案可能爆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);
}