codeforces-387B. George and Round

发布时间:2016-12-9 21:30:03 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"codeforces-387B. George and Round",主要涉及到codeforces-387B. George and Round方面的内容,对于codeforces-387B. George and Round感兴趣的同学可以参考一下。

codeforces-387B. George and Round 题意: 某人G准备了m个题目,难度分别为b1,b2,b3,,,,,bm 他需要使用n个题目,要求难度分别为 a1,a2,a3,an 他有“特异功能”,可以使任意一个题目减低任意难度 给出n,m 【a】【b】 问:使用他准备的题目,同时使用“特异功能”,他还要再准备多少题目 题意抽象: 1、我们尽量使用他所准备的题目来形成n个题目 2、对于所有能直接使用的b[i]==a[j](1<=i<=m,1<=j<=n) 3、对于剩下的题目,降低难度使得b[x]-c==a[y](1<=x<=m,1<=y<=n) 4、对所有没有对应的准备好的a[u]计数,答案就是其总数 解题思路: 1、用map<int ,int >存储<a[i],x>——x是难度为C的题目的个数 2、输入b[x]的同时,在【a】中检索b[i]==a[j](1<=i<=m,1<=j<=n),有的话,使用,否则存储到优先队列pb中 3、检索map<int ,int >,将未准备的题目的难度值取出,存储到优先队列pa中 4、将所准备的题目进行适当的降低难度处理,能用的就用 5,收集答案,输出 提交结果: 6088343 Feb 23, 2014 9:48:30 AM 20114045007 387B - George and Round GNU C++ Accepted 15 ms 400 KB 代码: #include<iostream> #include<map> #include<queue> using namespace std; int main(){ int n,m; //The number of the problem int x; map<int,int> ma; //to select the prepare problem priority_queue<int> pa,pb; //to select the simplyfiy problem cin>>n>>m; while(n--)cin>>x,ma[x]++; //save the problem information he need while(m--){ cin>>x; if(ma[x]>0)ma[x]--; //if the problem he prepare that he need we use it else pb.push(x); //else we save the problem he prepare but we not used } map<int,int>::iterator it=ma.begin(); //to serach the problem information he need but he has not prepared while(it!=ma.end()){ while(it->second--)pa.push(it->first); //to save it it++; } while(!pa.empty()&&!pb.empty()){ if(pa.top()<pb.top())pa.pop(),pb.pop(); //if a problem he has prepare can be simpylify to use we use it else pa.pop(),n++; //the problem he need ,but he not prepare and can't simpylify other problem for it we let him prepare agin } cout<<n+pa.size()+1; //why "-1",before cout the problem he hava to prepare agin n=-1 //pa.size(),,,the problem he need ,but he not prepare and can't simpylify other problem for it we let him prepare agin return 0; }

上一篇:re映射
下一篇:【完全背包】poj2063

相关文章

相关评论