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
ACM ICPC 2018 World Finals

Re:此题略坑 细节很多

Posted by lizimeng at 2016-08-17 14:42:38 on Problem 2431
In Reply To:此题略坑 细节很多 Posted by:BJ061008mms at 2015-04-12 15:49:08
> #include <iostream>
> #include <queue>
> #include <algorithm>
> using namespace std;
> struct _pair {
> 	int a;
> 	int b;
> };
> bool cmp(const _pair& left, const _pair& right){
> 	return left.a < right.a;
> }
> int main(){
> 	int N;
> 	cin>>N;
> 	_pair *t = new _pair[N];
> 	for(int i=N-1;i>=0;i--){
> 		cin >> t[i].a >> t[i].b;
> 	}
> 	int L ,P;
> 	cin>> L >> P;
> 	for (int i =N-1;i>=0;i--) {
> 		t[i].a = L-t[i].a;
> 	}
> 	sort(t,t+N,cmp);
> 	priority_queue<int> que;
> 	que.push(P);
> 	int cur = 0,ii=0,count=0;
> 	while(!que.empty()) {
> 		cur+=que.top();que.pop();
> 		if (cur>=L) break;
> 		count++;
> 		while(t[ii].a<=cur && ii<N) {
> 			que.push(t[ii].b);ii++;
> 		}
> 
> 	}
> 
> 	if(cur>=L)
> 		printf("%d\n", count);
> 	else
> 		puts("-1");
> 
> 	delete[] t;
> 
> 	return 0;
> }
> //===============================
> 1 输入的不是距离开始位置的距离,是相对结尾的距离
> 2 距离不一定是有序的要人工排序
> 3 没有结果输出-1 的格式很怪,但puts能搞定

真的是神坑啊。一开始注意到第一点,怎么也想不通样例。第二点也是坑,没事考排序干嘛。
谢谢大神提醒。

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