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

此题略坑 细节很多

Posted by BJ061008mms at 2015-04-12 15:49:08 on Problem 2431
#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