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 |
c++ 代码 O(nlogn)#include <cstdio> #include <algorithm> #include <queue> #include <vector> using namespace std; struct st { int d,f; } s[10005]; struct cmp { bool operator ()(st x, st y) { return x.f < y.f;//小的优先级高 }; }; bool cmp_1(st a,st b) { return a.d<b.d; } int n,L,P; int main() { scanf("%d",&n); for(int i=0; i<n; i++) { scanf("%d%d",&s[i].d,&s[i].f); } scanf("%d%d",&L,&P); priority_queue<st,vector<st>,cmp> q; for(int i=0; i<n; i++) { s[i].d=L-s[i].d; } sort(s,s+n,cmp_1); int i=0; int count=0; while(P<L) { for(;s[i].d<=P&&i<n;i++) { q.push(s[i]); } if(q.empty()) { printf("-1\n"); return 0; } P+=q.top().f; q.pop(); //printf("%d ",P); count++; } printf("%d",count); } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator