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

输入为两行。
第一行一个整数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);
}

输入包括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

#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);
}