首页 > 代码库 > 暑假集训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