滴滴2016.09.06校招オンライン筆記試験-2つのプログラミング問題

滴滴2016.09.06校招オンライン筆記試験-2つのプログラミング問題
1、連続サブ配列の最大和
タイトルの説明
1つの配列にはN個の要素があり、連続サブ配列の最大和を求める.例えば、[−1,2,1]、および最大の連続サブ配列は[2,1]、およびその和は3である.
説明の入力

     。
       n (1 <= n <= 100000),      n   ，    n  ，          32 int   。     。

出力の説明

             。

入力例

3
-1 2 1

出力例

3

分析:
参考解答:

#include 
#include 
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
",mx);
}

2、レストラン
タイトルの説明
あるレストランにはnつのテーブルがあり、各テーブルにはパラメータがあります.aが収容できる最大人数です.mロットのお客様がいて、各ロットのお客様には2つのパラメータがあります: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

分析:
貪欲なやり方.まず顧客を消費金額の降順、人数の昇順に並べ替える.そして、各波のお客様が現在最適なテーブルの容量を二分し、答えを維持すればいいので、答えが爆発する可能性があることに注意してください.この問題は裸の暴力では耐えられない.テーブルを分解できません.時間複雑度:O(mlogm+nlogm)
注意:結果はlong long(対応するprintfのフォーマットは%lldに制御)を使用する必要があります.long longを忘れた場合、サンプルは50%しか通過しません.
参考コード:

#include 
#include 
#include 
#include 

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 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
",ans);
}