「East!_XVI」不祥之刃

2015年4月4日3,2420

Background

卡特琳娜又要怒拿五杀了,怎么办啊?某无良设计师伊泽瑞尔笑了笑:“基兰,断网,重赛!”

Description

卡特琳娜要从 1 到 N 依次通过这 N 个李青[小学僧/盲僧], 并最终击杀第 N+1 个李青[Dopa 僧]。对于[小学僧],卡特琳娜可以击杀他得到一点法强和数量等同于该[小学僧]权值的金币; 对于[盲僧],如果卡特琳娜当前法强大于等于该[盲僧]的权值, 就会被该[盲僧]击杀。

现在卡特琳娜要击杀[Dopa 僧],就必须得到大于等于其权值的法强。问卡特琳娜满足击杀[Dopa 僧]的前提下最多能得到多少金币?

Input

第一行两个整数 N,M。M 表示[Dopa 僧]的权值。接下来 N 行每行一个字符和一个权值。如果是“d”,表示 student[小学僧] 如果是“p”,表示 perfect [ 盲僧 ]

Output

输出一个数如题,如果不能击杀[Dopa 僧],则输出“-1”。 Sample Input

42 d1 d2 p2 d1

Sample Output

Data Constraint

序号	N	特殊限制
1	0	–
2	[1,500]	–

3,4	[1,8000]	–
5,6	[1,500000]	暑假,全是小学僧。
7	[1,500000]	Ans == “-1”
8,9,10	[1,500000]	–

良心数据,无需 long long。 After Problem

鉴于伊泽瑞尔妹子太多,所以基兰把伊泽瑞尔移除了,但是他的原画被增加了粒子特效,现在伊泽瑞尔看起来更酷炫了。

题解

出题人18357：

首先我们可以处理出到每个点时最多能取几个。然后我们从头到尾扫一遍,然后把能取的都入优先队列,一旦超过到该点的限制,就让最小的出队。最后剩下的就是能取的所有点中最优集合。

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define pa pair<int,int>
#define ll long long 
#define mod 1000000007
using namespace std;
ll read()
{
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,m,ans;
char ch[500005][2];
int x[500005],mn[500005];
priority_queue<int,vector<int>,greater<int> >q;
int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)
	{
		scanf("%s",ch[i]+1);
		x[i]=read();
	}
	int now=inf;
	for(int i=n;i>=1;i--)
	{
		if(ch[i][1]=='p')now=min(x[i]-1,now);
		mn[i]=now;
	}
	for(int i=1;i<=n;i++)
	{
		if(ch[i][1]=='d')q.push(x[i]);
		while(q.size()>mn[i])q.pop();
	}
	if(q.size()<m){puts("-1");return 0;}
	while(!q.empty())
		ans+=q.top(),q.pop();
	printf("%d\n",ans);
	return 0;
}

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define pa pair<int,int>

#define ll long long

#define mod 1000000007

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,ans;

char ch[500005][2];

int x[500005],mn[500005];

priority_queue<int,vector<int>,greater<int> >q;

int main()

{

n=read();m=read();

for(int i=1;i<=n;i++)

{

scanf("%s",ch[i]+1);

x[i]=read();

}

int now=inf;

for(int i=n;i>=1;i--)

{

if(ch[i][1]=='p')now=min(x[i]-1,now);

mn[i]=now;

}

for(int i=1;i<=n;i++)

{

if(ch[i][1]=='d')q.push(x[i]);

while(q.size()>mn[i])q.pop();

}

if(q.size()<m){puts("-1");return 0;}

while(!q.empty())

ans+=q.top(),q.pop();

printf("%d\n",ans);

return 0;

}

« 「BC35」DZY Loves Topological Sorting 「CF526X」ZeptoLab Code Rush 2015 »

hzwer.com _ Home | http://hzwer.com

「East!_XVI」不祥之刃

分类目录

热门文章

Myfriends

近期评论