纪中集训2020.01.14【NOIP普及组】模拟赛C组总结——————小球
程序员文章站
2024-03-18 22:59:22
...
纪中集训2020.01.14【NOIP普及组】模拟赛C组总结——————小球
2.小球
太棒了吧！乍一看水题，再一看淼题，最后瞅一眼，不对！WHAT！ 背包还是贪心呀？然后陷入困境的我再无力翻身！终于打了半天背包，拿到了20分！
————————华丽的分割线———————
言归正传
题目大意：Description
给定n个不同颜色的球，每个球都有一个分数，同时有m个瓶子，每个瓶子都有固定的容量。现在，你必须把球放到瓶子里面。请编程计算最多能放多少个球到这些瓶子里。
Input
输入包含多组数据。
每组数据的第一行为两个整数n, m，分别表示球的个数和瓶子的个数。
接下来的n行，每一行包含一个整数p，表示相应的球的分数。
接下来的m行，每一行包含两个整数c和q, 分别表示每个瓶子的容量（最多能装多少个球）和分数上界（放进该瓶子的每个球的分数都不能超过p）。
当输入n，m均为0时，表示输入结束。
Output
对于每组数据，输出两个整数B和S，分别表示总共能放进瓶子里的球的最大数目，以及在这个前提下，放进瓶子里面的所有球的最大分数总和。B和S以空格隔开，每组答案独占一行。
Sample Input
2 1
2
3
1 2
2 2
4
5
2 4
2 5
0 0
Sample Output
1 2
2 9
巨佬们这套题的第三题？？？这么水！！！你居然用背包，~~没带脑子吧！
~~简单贪心就能AC呀！
分析：其实真的很简单，两个sort就行，一个排，球的分数，另一个排瓶子的容量和分数，然后贪心。都从大到小排，然后正着搜索双FOR 不会爆，尽量装，别忘了，可能有一个都装不下的瓶子！
附上AC Pascal代码：
var
a,b,c:array[0..1000005]of longint;
i,n,j,m,ans,sum:longint;
procedure qsorta(l,r:longint);
var
i,j,mid,t:longint;
begin
i:=l;
j:=r;
mid:=a[(i+j) shr 1+1];
repeat
while a[i]<mid do
begin
inc(i);
end;
while a[j]>mid do
begin
dec(j);
end;
if i<=j then
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
inc(i);
dec(j);
end;
until i>j;
if i<r then
begin
qsorta(i,r);
end;
if j>l then
begin
qsorta(l,j);
end;
end;
procedure qsortb(l,r:longint);
var
i,j,mid,t:longint;
begin
i:=l;
j:=r;
mid:=c[(i+j) shr 1+1];
repeat
while c[i]<mid do
begin
inc(i);
end;
while c[j]>mid do
begin
dec(j);
end;
if i<=j then
begin
t:=b[i];
b[i]:=b[j];
b[j]:=t;
t:=c[i];
c[i]:=c[j];
c[j]:=t;
inc(i);
dec(j);
end;
until i>j;
if i<r then
begin
qsortb(i,r);
end;
if j>l then
begin
qsortb(l,j);
end;
end;
begin
readln(n,m);
while(n<>0) or (m<>0) do
begin
for i:=1 to n do
begin
read(a[i]);
end;
for i:=1 to m do
begin
read(b[i],c[i]);
end;
qsorta(1,n);
qsortb(1,m);
j:=m;
ans:=0;
sum:=0;
for i:=n downto 1 do
begin
while (b[j]=0) and (j>0) do
begin
dec(j);
end;
if j=0 then
begin
break;
end;
if a[i]<=c[j] then
begin
inc(ans);
dec(b[j]);
sum:=sum+a[i];
end;
end;
writeln(ans,' ',sum);
readln(n,m);
end;
end.
附上AC C++代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int ans1,ans2,n,m,tot,j;
int a[207],r[207],f[207];
bool b[207];
bool cmp(int a,int b){return a>b;}
int main(){
scanf("%d%d",&n,&m);
while(n!=0&&m!=0){
ans1=ans2=0;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
scanf("%d%d",&r[i],&f[i]);
sort(a+1,a+n+1,cmp);
memset(b,1,sizeof(b));
for(int i=1;i<=m;i++){
tot=1;
j=0;
while(j<r[i]&&tot<=n){
if(a[tot]<=f[i]&&b[tot]){
b[tot]=0;
ans2+=a[tot];
j++;
}
tot++;
}
ans1+=j;
}
printf("%d %d\n",ans1,ans2);
scanf("%d%d",&n,&m);
}
return 0;
}