Codeforces Round #570 (Div. 3) G. Candy Box (hard version) (贪心,优先队列)

题意:你有\(n\)个礼物,礼物有自己的种类,你想将它们按种类打包送人,但是打包的礼物数量必须不同(数量,与种类无关),同时,有些礼物你想自己留着,\(0\)表示你不想送人,问你在送出的礼物数量最大的同时,尽可能的使自己喜欢的留下来,输出能送出的最大礼物数,以及这些礼物中自己不喜欢的数目.
题解:首先,我们肯定要让送出的礼物数最大,同时喜欢的最小,也就是送的礼物中,尽量让它的\(f\)是\(1\).这题考虑贪心,我们可以先对礼物数量进行排序,礼物数量相同让\(1\)多的排在前面,全部丢进优先队列里,用\(cur\)记录当前选的礼物数量,如果\(cur\)等于当前优先队列里拿出来的数量,由于\(cur\)表示上一次选的数量,所以当前礼物的数量就要\(-1\),注意!!!如果这个种类的礼物的\(f=1\)的数量和礼物数相同,那么\(f=1\)的数量也要\(-1\),因为你全是\(1\),去掉一个,\(f=1\)当然也要减一(这不是废话吗?).

代码:

struct misaka{

	int a;

	int f;

	bool operator < (const misaka  & mikoto) const {

		if(a==mikoto.a) return f<mikoto.f;

		return a<mikoto.a;

	}

}e;

int t;

int n;

map<int,int> mp1,mp2;

priority_queue<misaka,vector<misaka>> h;

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin>>t;

    while(t--){

    	cin>>n;

    	int ans1=0;

    	int ans2=0;

    	mp1.clear();

    	mp2.clear();

    	rep(i,1,n){

    		int x,f;

    		cin>>x>>f;

    		mp1[x]++;

    		mp2[x]+=f;

    	}

    	for(auto w : mp1){

    		e={w.se,mp2[w.fi]};

    		h.push(e);

    	}

    	int cur=-1;

    	while(!h.empty() && cur!=0){

    		misaka tmp=h.top();

    		h.pop();

    		int val=tmp.a;

    		int f=tmp.f;

    		if(cur!=val){

    			ans1+=val;

    			ans2+=f;

    			cur=val;

    		}

    		else{

    			if(val==f){

    				val--;

    				f--;

    			}

    			else val--;

    			h.push({val,f});

    		}

    	}

    	while(!h.empty()) h.pop();

    	cout<<ans1<<' '<<ans2<<'\n';

    }

    return 0;

}

巴特西

Codeforces Round #570 (Div. 3) G. Candy Box (hard version) (贪心,优先队列)

最新文章

热门文章