首页 > 代码库 > 暑假集训day12
暑假集训day12
今天算是结业考了。
我很弱,才170。
下面给出我AC的一道题。
beatbear
好像没有题面是吧
那就不管它吧
题意,给出n个关卡,关卡分2种:d和p。
如果是d,后面会跟着一个数,表示取这个点得到的值。
如果是p,后面会跟着一个数,表示在其之前取的点数不能大于或等于这个数。
另有一个m,表示在过了n个关卡之后如果取的点数要不小于m,
如果小于或等于表示无解,否则输出取点得到的值的总和最大的。
我用一个优先队列,如果遇到d就存入队列,遇到p就pop,直到之前取的点数小于给出的数。
然后莫名其妙的就跑得比标程快了,
果然是“玄学出正解,暴力踩标程”。
其实这个是正解
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<vector> using namespace std; inline int read(){ int num=0,t=1;char c=getchar(); while(c>‘9‘||c<‘0‘){if(c==‘-‘)t=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){num=num*10+c-‘0‘;c=getchar();} return num*t; } int n,m,num=0;long long sum=0; priority_queue< int,vector<int>,greater<int> >q; int main() { freopen("beatbear.in","r",stdin); freopen("beatbear.out","w",stdout); n=read();m=read(); for(int i=1;i<=n;i++){ char c=getchar(); while(c!=‘p‘&&c!=‘d‘)c=getchar(); int x=read(); if(c==‘d‘){sum+=x;num++;q.push(x);} else{ while(num>=x){ int tmp=q.top();q.pop(); num--;sum-=tmp; } } } if(num<m)puts("Fox can not beat bear."); else cout<<sum; return 0; }
本文由Yzyet编写,网址为www.cnblogs.com/Yzyet。非Yzyet同意,禁止转载,侵权者必究。
暑假集训day12
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。