題意簡要的說就是N件任務(wù)，每件任務(wù)i有期限d
i和收益p
i，每個時刻能同時做n個任務(wù)，求最大獲益。
貪心策略是這樣的:先對任務(wù)按照收益排序，然后盡可能地往靠近期限的地方丟，這里用到并查集來優(yōu)化，如果某個時刻已經(jīng)被占用n次了，則將其與前面一個格子合并，具體細(xì)節(jié)注意下就可以了
1 # include <cstdio>
2 # include <algorithm>
3 using namespace std;
4 struct node
5 {
6 int p,d;
7 }data[10005];
8 bool cmp(const node &a,const node &b)
9 {
10 return a.p>b.p;
11 }
12 int set[10005];
13 int co[10005];
14 int find(int pos)
15 {
16 if(set[pos]==pos)
17 return pos;
18 else return set[pos]=find(set[pos]);
19 }
20 int num,l;
21 int main()
22 {
23 while(scanf("%d%d",&num,&l)!=EOF)
24 {
25 for(int i=0;i<num;i++)
26 scanf("%d%d",&data[i].p,&data[i].d);
27 for(int i=0;i<=10000;i++)
28 set[i]=i,co[i]=l;
29 sort(data,data+num,cmp);
30 int total=0;
31 for(int i=0;i<num;i++)
32 {
33 if(co[find(data[i].d)]==0) continue;
34 else
35 {
36 co[find(data[i].d)]--;
37 total+=data[i].p;
38 if(!co[find(data[i].d)])
39 {
40 for(int j=data[i].d;j>=0;j--)
41 {
42 if(co[find(j)])
43 {
44 set[find(data[i].d)]=find(j);
45 break;
46 }
47 }
48 }
49 }
50 }
51 printf("%d\n",total);
52 }
53 return 0;
54 }
55