| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:此题略坑 细节很多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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator