优先队列(挑程)poj 2431

每次写poj的题都很崩溃,貌似从来没有一次一发就ac的,每次都有特别多的细节需要考虑。还有就是自己写的太粗糙了,应该把每种情况都想到的,总是急着交,然后刷一页wa。

优先队列直接用stl就可以,简单实用。

 #include <iostream>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <stack>
#include <queue>
using namespace std;
const double Pi=3.14159265358979323846;
typedef long long ll;
const int MAXN=+;
const int dx[]={,,,,-};
const int dy[]={,-,,,};
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll mod=1e9+;
struct node{
int p,d;
}a[MAXN];
bool cmp(node a,node b)
{
return a.d>b.d;
}
int main()
{
int n;scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d",&a[i].d,&a[i].p);
}
int L,P;
scanf("%d%d",&L,&P);
for(int i=;i<=n;i++)
{
a[i].d=L-a[i].d;
}
sort(a+,a+n+,cmp);
/*for(int i=1;i<=n;i++)
{
cout <<a[i].d<<endl;
}*/
int ans=;
priority_queue <int> pque;
if(n==&&P-L<)
{
puts("-1");
return ;
}
for(int i=n;i>=;i--)
{
int dis=a[i].d-a[i+].d; if(dis>P)
{
while(dis>P&&!pque.empty())
{
P+=pque.top();
pque.pop();
ans++;
}
if(dis>P)
{
puts("-1");
return ;
}else
{
P=P-dis;
}
} else
{
P=P-dis;
}
pque.push(a[i].p);
}
int l=L-a[].d;
while(!pque.empty()&&P<l)
{
P+=pque.top();
ans++;
pque.pop();
}
if(P<l) puts("-1");
else printf("%d\n",ans);
return ;
}
上一篇:【BZOJ1269/1507】[AHOI2006]文本编辑器editor Splay


下一篇:cygwin远程操作linux