欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

纪中集训2020.01.14【NOIP普及组】模拟赛C组总结——————小球

程序员文章站 2024-03-18 22:59:22
...

纪中集训2020.01.14【NOIP普及组】模拟赛C组总结——————小球

2.小球
太棒了吧!乍一看水题,再一看淼题,最后瞅一眼,不对!WHAT! 背包还是贪心呀?然后陷入困境的我再无力翻身!终于打了半天背包,拿到了20分

————————华丽的分割线———————

言归正传

2.小球

题目大意: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;
}

END!

下一题:纪中集训2020.01.14【NOIP普及组】模拟赛C组总结——————小明的游戏