codeforces+C. Multi-Subject Competition+技巧

题目链接：http://codeforces.com/problemset/problem/1082/C
题目大意：

有n个人，m个竞赛，（1≤n≤10^5, 1≤m≤10^5)
每个人熟悉一个竞赛si，并且熟悉的本领为ri（ri可以为负）
现在让你选择去参加竞赛的人，对应选择的要求：对于有人去的这些竞赛，去的人数必须相同，有的竞赛可以没人去。

问你去的人的本领总和最大是多少？

思路：

但是复杂度为O（n*m）。
但是可以用边求前缀和边求C[i]数组，复杂度为O（n）

 for(int i=1;i<=m;i++)
    {
        sort(v[i].begin(), v[i].end(), ru);//排序
        long long s=0;
        for(int j=0;j<v[i].size();j++)
        {
            s+=v[i][j];
            if(s>0)/*如果前缀和>0那么选择j个人，一定会选这个学科，所以c[j]+=s;*/
                c[j]+=s;
            else
                break;
        }
    }

思路：一个好的技巧

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 100005;

vector<int> v[N];
ll c[N];
int ru(int a, int b){return a>b;}

int main()
{
    fill(c, c+N, 0);
    int n, m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        int x, y;
        scanf("%d%d",&x, &y);
        v[x].push_back(y);
    }
    
    for(int i=1;i<=m;i++)
    {
        sort(v[i].begin(), v[i].end(), ru);//排序
        long long s=0;
        for(int j=0;j<v[i].size();j++)
        {
            s+=v[i][j];
            if(s>0)/*如果前缀和>0那么选择j个人，一定会选这个学科，所以c[j]+=s;*/
                c[j]+=s;
            else
                break;
        }
    }
    cout<<*max_element(c, c+100002)<<endl;

	return 0;
}