SGU 171 Sarov zones （贪心）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目 SGU 171

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

题目意思就是说有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更小的更多的机会

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

实现见代码

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<queue>
#include<algorithm>
#include<cmath>
#include<stdlib.h>
using namespace std;
#define MAX(a,b) (a > b ? a : b)
#define MIN(a,b) (a < b ? a : b)
#define MAXN 500005
#define INF 1000000007
#define mem(a) memset(a,0,sizeof(a))
#define eps 1e-15 struct ZONE{int num,q,index;}zone[];//num招纳参赛人员的个数，Q值，以及保存这个地区最初编号（防止排序后打乱）
struct PERSON{int p,w,index,z;}per[];//P值，W值，编号，以及选择的地区
int K,N; int cmp_zone(ZONE a,ZONE b)//按照Q值的从大到小排序，这样的话每次就只需要找到满足P>Q时，Q最大的哪一个
{
return a.q > b.q;
} int cmp_per(PERSON a,PERSON b)//按照W的降序以及P的升序排序
{
if(a.p != b.p)return a.w > b.w;
return a.p < b.p;
} int cmp_index(PERSON a,PERSON b)//按照参赛人员最初的编号排序，保证输出的顺序
{
return a.index < b.index;
} int main()
{
while(~scanf("%d", &K))
{
int i;N=;
for(i=;i<K;i++)
{
scanf("%d",&zone[i].num);
zone[i].index = i+;//保存编号
N+=zone[i].num;
}
for(i=;i<K;i++)
{
scanf("%d",&zone[i].q);
}
sort(zone, zone+K,cmp_zone);//排序
for(i=;i<N;i++)
{
scanf("%d",&per[i].p);
}
for(i=;i<N;i++)
{
scanf("%d",&per[i].w);
per[i].index = i;
per[i].z = -;
}
sort(per,per+N,cmp_per);
int p = , z = , nz = ;//p表示选择到了第p个人，Q值最大而且还没有选择完全的地区编号
while(p<N && nz<N)
{
while(!zone[nz].num)nz++;//找到目前还没有被选择的Q值最大的地区
z=nz;
while((per[p].p <= zone[z].q || !zone[z].num ) && z<N)//找到满足P>Q的第一个地区
{
z++;
}
if(z<N)
{
per[p].z = zone[z].index;
zone[z].num--;
}
else if(z == N)
{
per[p].z = zone[nz].index;
zone[nz].num--;
}
p++;
}
sort(per,per+N,cmp_index);
for(i=;i<N;i++)
{
printf("%d%c",per[i].z,i==N-?'\n':' ');
}
}
return ;
}