纪中集训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;
}