代码

#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
struct ntype
{
int h,t;
};
ntype a[50010];
priority_queue <int> q;

bool cmp(const ntype &x,const ntype &y)
{
return(x.h<y.h);
}

int main()
{
int n,time=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d %d",&a[i].h,&a[i].t);

sort(a+1,a+n+1,cmp);

for(int i=1;i<=n;i++)
{
if(time+a[i].t<=a[i].h)
{
time+=a[i].t;
q.push(a[i].t);
continue;
}

if(q.top()>a[i].t)
{
time=time-q.top();
q.pop();
q.push(a[i].t);
time+=a[i].t;
continue;
}
}
printf("%d",q.size/*返回优先队列中的元素个数*/());

return 0;
}

先按照h[i]从小到大排序，然后每次循环维护一下优先队列

type
node=record
x,y:longint;
end;
var
n,tot,line,i,j,muqian:longint;
a:array[0..50555] of node;
z:array[0..700] of int64;
function

min(aa,bb:int64):int64;
begin
if aa>bb then exit(bb) else exit(aa);
end;
procedure
qsort(l,r:longint);
var
xx,yy,mid,t,t1,midd:longint;
begin
xx:=l;
yy:=r;
mid:=a[(xx+yy) div 2].y;
midd:=a[(xx+yy) div 2].x;
repeat
while (a[xx].y<mid) or (a[xx].y=mid) and (a[xx].x<midd) do inc(xx);
while (a[yy].y>mid) or (a[xx].y=mid) and (a[xx].x>midd) do dec(yy);
if xx<=yy then
begin
t:=a[xx].y;
t1:=a[xx].x;
a[xx].y:=a[yy].y;
a[xx].x:=a[yy].x;
a[yy].y:=t;
a[yy].x:=t1;
inc(xx);
dec(yy);
end;
until (xx>yy);
if xx<r then qsort(xx,r);
if yy>l then qsort(l,yy);
end;
begin

readln(n);
for i:=1 to n do begin read(a[i].y,a[i].x); end;
fillchar(z,sizeof(z),$FF); z[0]:=0;
qsort(1,n);
for i:=1 to n do begin
for j:= min(700,n) downto 1 do
begin
if (z[j-1]+a[i].x<=a[i].y) and (z[j-1]<>-1) then
begin
if z[j]=-1 then z[j]:=z[j-1]+a[i].x;
z[j]:=min(z[j],z[j-1]+a[i].x);
end;
end;
end;
for i:=700 downto 1 do
if z[i]<>-1
then begin writeln(i);
exit; end;
readln;
end.
这道题我是runtime 第7 第8 个点，为什么啊

用堆来调整

连堆都没用。。

KP AC了。。

先把所有人按t排序，然后贪心，建立一个极大堆，堆中元素表示被救的人。如果第i人能救就直接把它放入，否则看看把最大的那个人移走之后他能否就，能的话就把最大的那个人移走，放入他。

最后堆的元素个数就是答案。

Accepted 有效得分：100 有效耗时：143ms

此题其实不怎么难

总体来说就是

排序加特殊的最长递增序列

___|\__|\__|__begin___|\__|\__|

排序把 最晚的治疗完成时刻 最早的提到前面

至于救不救就让DP来选

这题的DP 可用背包（背包很容易超时 优化不好的得

好题呀`~`

最长递增子序列变形题？

读入要用longint啊！！！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 166ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：191ms

贪心太复杂了，什么线段树之类的，我不会的说！！！

z[i] 记录救援人数达到 I 时最小的时间

易证z是单调递增的，当Z[J]+T>h[i]时可以BREAK

所以不会超时

不会线段树，树状数组的可以用这种方法

不BREAK也能过的说！！

为什么不BREAK也能过呢

H 最大36000 T最小 60

36000/60=600

最多救600个人

50000*600=30000000

实际上的复杂度远远小于30000000

所以

不会超时

虽然不能秒杀，但是是个比较基础的方法！！！

贪心，可以用调整的方法证明。

快排问题

感谢本校翁大牛让我对快排又有了更进一步的认识！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

这是一道动规题，在下五体膜拜各位神牛的贪心算法！

治疗顺序一定是按照h不降,且若有一段h相同的对象，则随意交换这些对象都可以满足。该结论可以通过证明对相邻的递降子串交换总权不劣得到。

接下来类似NightElf的做法：

先按照h排序

令d[i]表示前i个能救援的最大数目。

令f[i][j]表示前i个，救援j个的最少时间。

对于d[i]:若f[d]+t[i]h[i]那么f[i][j]:=f[d];

若jd[i]：

若f[j-1]+t[i]

贪心。用堆维护。

把建筑抢修的程序拿来加一个=号就AC了。

贪心+线段树维护

楼下正解

咋那么麻烦捏？

先按h小到大排

然后搞个极大堆

把所有伤员的t一个一个加进堆中

如果 堆总和+现在伤员的t

终于艰难地AC，和CTSC2007那题是一样的……

看了题解，知道是贪心，还要写线段树和树状数组……

结果线段树写错了一个小地方（区间加一个数递归返回时没维护）调了半天……

但这样还是70分，最后才知道会存在访问这样的区间(n+1,n)，特殊判断一下就AC了……

算导上的貌似不行，这题跟建筑抢修实际上是一道题。