首页 > 代码库 > Luogu P1094 纪念品分组

Luogu P1094 纪念品分组

2024-09-27 01:08:39   206人阅读

Description

详见https://www.luogu.org/problem/show?pid=1094

Solution

> -------
这是一道不错的贪心，虽然代码很短，但是证明还是挺考思维的
> -------
先从大到小排序
> -------

刚开始想将最大的和他能搭配的最大的搭配，比如图中a可以和c和d，但是我想选择c，

技术分享
> -------
但是仔细一想其实没这个必要，
因为 ，如果a>b,c>d  而且 a+c<=w 那么b+c<=w  也就是说无论 a&c，b&d 或a&d，b&c都是两种

技术分享
于是我们的搭配完全没有必要交叉，交叉的结果也是等于不交叉的
> -------
所以我们可以从外向内匹配【保证不交叉】
如果可以匹配就匹配不能就自己放一个盒子

Codes

 1 var 2   n,w,i,j,ans:Longint; 3   a:array[1..30000] of longint; 4   b:array[1..30000] of Boolean; 5  6 procedure qsort(l,r: longint); 7 var 8    i,j,x: longint; 9    y:longint;10 begin11     i:=l;   j:=r;12     x:=a[(l+r) div 2];13    repeat14      while (a[i]>x)  do inc(i);15      while  (x>a[j]) do dec(j);16      if not(i>j) then17        begin18          y:=a[i];  a[i]:=a[j];   a[j]:=y;19          inc(i);   j:=j-1;20        end;21    until i>j;22    if l<j then qsort(l,j);23    if i<r then qsort(i,r);24 end;25 26 begin27    // assign(input,‘t.in‘);  assign(output,‘t.out‘);28     reset(input);  rewrite(output);29 30     readln(w);31     readln(n);32     for i:= 1 to n do readln(a[i]);33 34     qsort(1,n);35 36     i:=1;  j:=n;37     while i<=j do38     begin39         if a[i]+a[j]<=w then dec(j) ;40         inc(i);41         ans:=ans+1;42     end;43 44     writeln(ans);45     close(input); close(output);46 end.

 

Luogu P1094 纪念品分组


联系
我们