题解 [CF332C] Students' Revenge

题面

解析

辣鸡题面毁我青春

因为翻译的题面中写了一句(剩下的n−k个不会完成).

所以就以为剩下的(n-k)个都会算上不满意值.

(然而事实是只有(p-k)个...)

首先根据主席的规则,我们可以先钦定(p-k)个绝对不会被选的任务,

把(b)从大到小,再把(a)从小到大取最后面就行了.

(应该很容易理解吧...)

然后再把剩下的按(a)从大到小,

再把(b)从大到小排序,取前(k)个就是白头发最多的情况了.

这里把(b)从大到小是因为剩下的(p-k)个还要使不满意度最大,

所以从大到小的话就有了更多机会.

然后考虑剩下的(p-k)个,

因为之前钦定的不一定是不满意度最大的情况,

因此我们要再按第一次的顺序,

取已经取了的前(k)个中在最后面的任务的后面(p-k)个就行了.

这里听起来可能有点绕口...

因为我们要保证剩下的(p-k)个不能干扰前面的(k)个(即在主席的规则中优先度更高).

再自己(yy)下应该就行了.

还有一点要注意的是,

因为有两个任务可能(a,b)都相等,

因此两次排序的结果可能不一样(因为这个WA到吐...)

所以在排序的时候把编号作为第三关键字就好了.

code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fre(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
using namespace std;

inline int read(){
	int sum=0,f=1;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
	return f*sum;
}

const int N=200005;
struct node{int x,y,tag,id,pos;}a[N],b[N];
int n,K,P,sum=0x3f3f3f3f,ret=0;

inline bool cmp(node a,node b){
	return a.y!=b.y? a.y<b.y:a.x>b.x;
}

inline bool cmp1(node a,node b){
//	if(a.tag!=b.tag) return a.tag<b.tag;
	if(a.x!=b.x) return a.x>b.x;
	return a.y>b.y;
}

inline bool cmp2(node a,node b){return a.y!=b.y? a.y>b.y:a.x<b.x;}

signed main(){
	n=read();P=read();K=read();
	for(int i=1;i<=n;i++) a[i].x=read(),a[i].y=read();
	for(int i=1;i<=n;i++) a[i].id=i;
	sort(a+1,a+n+1,cmp2);
	memcpy(b,a,sizeof(b));
	for(int i=1;i<=n;i++) a[i].pos=i;
	int ss=P-K;
	sort(a+1,a+n-ss+1,cmp1);
	for(int i=1;i<=K;i++) printf("%d ",a[i].id);
	for(int i=1;i<=K;i++) ret=max(ret,a[i].pos);
//	sort(a+ret+1,a+n+1,cmp2);
	for(int i=1;i<=ss;i++){
		printf("%d ",b[i+ret].id);
	}
	
//	for(int i=1;i<=n;i++) if(a[i].tag) printf("%d ",a[i].id);
	puts("");
	return 0;
}