| ||||||||||
| 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