LINK:BNUOJ 26475 Cookie Selection
题意:
你在不停的输入数字a1,a2,a3,......,ak,当你输入#时,就把已输入数字中的第k/2+1删除,然后剩下的数字又组成一个新的数列a1,a2,......,a(k-1)。把删除的数输出来~╮(╯▽╰)╭
刚开始理解错了题意......各种WA......想半天还不知道错哪.....最后搞清,自己压根连题目都弄错了......就没有再继续战斗的想法了~~~~(>_<)~~~~
该题要用到优先队列......具体方法参见代码ORZ......
代码【一】:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
priority_queue<int> p;
priority_queue<int,vector<int>,greater<int> > q;
char str[];
void doit(){
while(p.size()>q.size()){
q.push(p.top());
p.pop();
}
while(q.size()>p.size()+){
p.push(q.top());
q.pop();
}
}
int main(){
int i,j,k;
while(~scanf("%s",str)){
if(str[]=='#'){
printf("%d\n",q.top());
q.pop();
doit();
}
else{
sscanf(str,"%d",&k);
if(!q.empty()&&k>q.top()) q.push(k);
else p.push(k);
doit();
}
}
return ;
}
//memory:3132KB time:712ms
代码【二】://这代码.......不是很懂啊~
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <set>
using namespace std;
typedef set<double> si;
int main(void)
{
si X;
si::iterator it = X.begin();
char str[];
while (scanf("%s", str) == )
{
if (str[]== '#')
{
printf("%.0lf\n", *it);
X.erase(it++);
if (X.size() % )
--it;
}
else
{
double x = atoi(str)+0.4*drand48(); //atoi(str)能把字符串str转化为数字,drand48()产生一个随机的double数
X.insert(x);
if (X.size() == )
it = X.begin();
else
{
if (x < *it)
--it;
if (X.size() % == ) ++it;
}
}
}
return ;
}
//memory:10792KB time:1288ms