Question

pascal做题

1167: 合照
时间限制: 1 Sec 内存限制:
64 MB
提交: 276 解决:
147
[提交][状态][讨论版]
题目描述

歌手SJM到幼儿园跟小朋友玩，他到达的时候小朋友已经争着积木玩了。小朋友都想要更多的积木砌一个自己喜欢的图形，砌玩就可以和SJM合照。同时，SJM手上还有一些积木，他可以把手里的这些积木全部给一个小朋友，然后等该小朋友砌完后就可以收回所发的积木和该小朋友原先手里的积木。但SJM想知道他最多可以和多少个小朋友合照，你能帮助他吗？

输入

输入第一行包括两个正整数N和S，中间用空格隔开，其中1<=N<=1000,1<=S<=10000,表示一共有N位小朋友，
SJM手上有S块积木。以下有N行，每行有两个正整数，a和b(1<=a<=10^5,1<=b<=10^9),表示每个小朋友手上有的积木数量和还需要的积木数量。

输出

输出SJM最多可以和多少个小朋友合照。

样例输入 Copy

2 2
1 4
2 1

样例输出 Copy

2

提示

输入样例2：
2 2
1 4
1 1

输出样例2：
1

样例解释:

样例1：有2个小朋友，SJM手里一开始有2块积木，第1个小朋友手里有1块积木，他还需要4块积木，第2个小朋友手里有2块积木，他还需要1块积木，SJM可以先满足第2个小朋友的需求，即给第2个小朋友1块积木，这样第2个小朋友就可以砌完图形，然后把所有的积木给SJM，这样SJM就有4块积木，此时可以满足第1个的需求，所有可以和2个小朋友合照。

样例2：SJM一开始只能满足第2个小朋友的需求，然后积木数量变为3，还是不能满足第1个小朋友的需求，所以最多只能和1个小朋友合照。

来源

Answer 1

（快排+模拟）
观察题目可以发现，与一个小朋友合照后其实并不需要付出任何代价，而且合照后S必然会增加，故应该尽可能多的与小朋友合照，即优先选取需要积木数最少的小朋友合照。
程序：
var n,s,ans:longint;
a,b:array[1..1000]of longint;
//--------------------------------------------------------------------------------------------------------------------
procedure swap(var x,y:longint);
var z:longint;
begin
z:=x;x:=y;y:=z;
end;
procedure qsort(l,r:longint);
var x,y,z:longint;
begin
x:=l;y:=r;z:=b[(l+r)div 2];
repeat
while b[x]<z do inc(x);
while b[y]>z do dec(y);
if x<=y then
begin
swap(b[x],b[y]);
swap(a[x],a[y]);
inc(x);
dec(y);
end;
until x>y;
if x<r then qsort(x,r);
if y>l then qsort(l,y);
end;
//--------------------------------------------------------------------------------------------------------------------
procedure init;
var i:longint;
begin
readln(n,s);
for i:=1 to n do
readln(a[i],b[i]);
end;
procedure main;
var i:longint;
begin
qsort(1,n);
for i:=1 to n do
if s>=b[i] then
begin
inc(s,a[i]);
inc(ans);
end
else break;
writeln(ans);
end;
//--------------------------------------------------------------------------------------------------------------------
begin
init;
main;
end.