Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:优先队列,特别注意的地方就是题目并不是一定按顺序输入。一道简单的题目。附代码

Posted by 202009504139 at 2023-04-28 09:39:22 on Problem 2431
In Reply To:优先队列,特别注意的地方就是题目并不是一定按顺序输入。一道简单的题目。附代码 Posted by:13408100238 at 2014-08-09 09:41:44
> #include"iostream"
> #include"cstdio"
> #include"cstring"
> #include"queue"
> #include"algorithm"
> using namespace std;
> const int ms=1e5+5;
> struct node
> {
> 	int a,b;
> }a[ms];
> bool cmp(const node &a1,const node &a2)
> {
> 	return a1.a<a2.a;
> }
> int n,l,p;
> void input()
> {
> 	scanf("%d",&n);
> 	for(int i=0;i<n;i++)
> 	{
> 		scanf("%d%d",&a[i].a,&a[i].b);
> 	}
> 	scanf("%d%d",&l,&p);
> 	for(int i=0;i<n;i++)
> 		a[i].a=l-a[i].a;
> 	a[n].a=l;
> 	a[n].b=0;
> 	n++;
> 	sort(a,a+n,cmp);
> }
> void solve()
> {
> 	int i,d,pos=0,tank=p,ans=0;
> 	priority_queue<int> q;
> 	for(i=0;i<n;i++)
> 	{
> 		d=a[i].a-pos;
> 		while(tank<d)
> 		{
> 			if(q.empty())
> 			{
> 				puts("-1");
> 				return ;
> 			}
> 			tank+=q.top();
> 			q.pop();
> 			ans++;
> 		}
> 		tank-=d;
> 		pos=a[i].a;
> 		q.push(a[i].b);
> 	}
> 	cout<<ans<<endl;
> 	return ;
> }
> int main()
> {
> 	input();
> 	solve();
> 	return 0;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator