SGU 171 Sarov zones （贪心）

相当好的贪心的题目！！！！！

题目意思就是说有K个赛区招收参赛队员，每个地区招收N[i]个，然后每个地区都有一个Q值，而N[i]的和就是N，表示总有N个参赛队员，每个队员都有他自己的P值，和他的权值W，只有当一个队员的P大于某一个地区的Q值时，权值W才能被记录在内，问怎样让着N个参赛队员选择地区才能让权值和最大。

贪心的思路就是按照权值W贪心

1、先按W的降序排序，优先考虑权值交大的。

2、歪了不影响后面的参赛队员，W较大的而且满足P>Q的，让其参加p>Q时Q最大的那一个。所以Q值按照降序排序。

3、如果某一个找不到一个Q使得P>Q，那么就让他参加Q最大的那一个赛区，这样可以给后面W更小的更多的机会

（这才发现贪心实在用的太巧秒了，以后更加的好好钻研）

实现见代码

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<map>
 5 #include<vector>
 6 #include<set>
 7 #include<stack>
 8 #include<queue>
 9 #include<algorithm>
10 #include<cmath>
11 #include<stdlib.h>
12 using namespace std;
13 #define MAX(a,b) (a > b ? a : b)
14 #define MIN(a,b) (a < b ? a : b)
15 #define MAXN   500005
16 #define INF 1000000007
17 #define mem(a) memset(a,0,sizeof(a))
18 #define eps 1e-15
19 
20 
21 struct ZONE{int num,q,index;}zone[16005];//num招纳参赛人员的个数，Q值，以及保存这个地区最初编号（防止排序后打乱）
22 struct PERSON{int p,w,index,z;}per[16005];//P值，W值，编号，以及选择的地区
23 int K,N;
24 
25 int cmp_zone(ZONE a,ZONE b)//按照Q值的从大到小排序，这样的话每次就只需要找到满足P>Q时，Q最大的哪一个
26 {
27     return a.q > b.q;
28 }
29 
30 int cmp_per(PERSON a,PERSON b)//按照W的降序以及P的升序排序
31 {
32     if(a.p != b.p)return a.w > b.w;
33     return a.p < b.p;
34 }
35 
36 int cmp_index(PERSON a,PERSON b)//按照参赛人员最初的编号排序，保证输出的顺序
37 {
38     return a.index < b.index;
39 }
40 
41 int main()
42 {
43     while(~scanf("%d", &K))
44     {
45         int i;N=0;
46         for(i=0;i<K;i++)
47         {
48             scanf("%d",&zone[i].num);
49             zone[i].index = i+1;//保存编号
50             N+=zone[i].num;
51         }
52         for(i=0;i<K;i++)
53         {
54             scanf("%d",&zone[i].q);
55         }
56         sort(zone, zone+K,cmp_zone);//排序
57         for(i=0;i<N;i++)
58         {
59             scanf("%d",&per[i].p);
60         }
61         for(i=0;i<N;i++)
62         {
63             scanf("%d",&per[i].w);
64             per[i].index = i;
65             per[i].z = -1;
66         }
67         sort(per,per+N,cmp_per);
68         int p = 0, z = 0, nz = 0;//p表示选择到了第p个人，Q值最大而且还没有选择完全的地区编号
69         while(p<N && nz<N)
70         {
71             while(!zone[nz].num)nz++;//找到目前还没有被选择的Q值最大的地区
72             z=nz;
73             while((per[p].p <= zone[z].q || !zone[z].num ) && z<N)//找到满足P>Q的第一个地区
74             {
75                 z++;
76             }
77             if(z<N)
78             {
79                 per[p].z = zone[z].index;
80                 zone[z].num--;
81             }
82             else if(z == N)
83             {
84                 per[p].z = zone[nz].index;
85                 zone[nz].num--;
86             }
87             p++;
88         }
89         sort(per,per+N,cmp_index);
90         for(i=0;i<N;i++)
91         {
92             printf("%d%c",per[i].z,i==N-1?'
':' ');
93         }
94     }
95     return 0;
96 }