纪念品分组 （C++代码）

解题思路:





注意事项:





参考代码:

本题思路：比较经典的贪心，读入之后快排，定义两个指针z，y（其实就是两个变量QAQ），分别从0和n-1开始，如果左侧的小数加上右侧的大数比规定范围w小，就把它们俩分在一组，ans++，z++，y--，不然就把右侧的数单独分在一组，ans++，y--，最后输出ans

#include<cstdio>#include<iostream>#include<algorithm>//sort必备万能头文件using namespace std;int a[1000000],ans;//定义（这里插一句，本人喜欢把数组和最后结果放在函数外定义，这样使它们的初值默认为0，不容易犯没有初始化的错误）int main(){//过程华丽开始
   int n,w;//定义
   scanf("%d",&w);//读入
   scanf("%d",&n);//读入
   for(int i=0;i<n;i++)        scanf("%d",&a[i]);//读入
   sort(a,a+n);//调用快排函数sort
   int z=0,y=n-1;//定义指针（变量）
   while(z<=y){//开始主要的处理
       if(a[z]+a[y]<=w){ans++;z++;y--;}//如果能装下，就装
       else {y--;ans++;}//不能装下，将大的分为单独的一组
   }    printf("%d\n",ans);//输出
   return 0;//过程完美结束}

评论

还没有评论

评论

作者: Aeber 更新时间: 2017-10-30 20:34  在Ta的博客查看  2 

蒟蒻什么算法都没学过，但是了解过贪心的思路

用了一个数组一个布尔量数组，思路是排序后从最贵的开始查看，

如果和最便宜的相加后符合条件则计数++标记马克上，

便宜的下标符合条件后再往上，但贵的无论是否单独一组都只看一遍

最后检查一遍，没有马克过的数据就是单独一组，计数++

好处就是小白都能看懂

#include<iostream>#include<algorithm>using namespace std;bool judge(int a,int i,int n){    if (i+a<=n)        return true;    else return false;

}//闲着没事干写了个函数

int main(){    int max_price,num;    cin>>max_price>>(num);    bool check[num+1];    int item[num+1];//一个数组一个布尔量数组
   for (int i=1;i<=num;i++)
   {        cin>>item[i];
       check[i]=true;//为了方便写成这样，其实是没有分组
   }
   sort (item+1,item+num+1);    int m=1,ans=0;    for (int i=num;i>0;i--)
   {        if (check[i]==false) continue;//如果这个商品已经被拿过，直接跳过
               //其实可以用break
       if (judge(item[i],item[m],max_price))
       {
           check[i]=false;
           check[m]=false;//马克两件已分组奖品
           m++;//便宜下标++；
           ans++;//计数++
       }
   }    for (int i=1;i<=num;i++)        if (check[i]) ans++;//检查单独一组
   cout<<ans<<endl;    return 0;
}

评论

还没有评论

评论

作者: xukuan 更新时间: 2017-10-26 13:10  在Ta的博客查看  2 

贪心，递归，排序

if a[i]+a[j]<w then ...

               else ...

.pas

var
w,n,i,j,t,count:longint;
a:array[0..30010] of longint;procedure qsort(var a:array of longint; l,r:longint);//快速排序
var
 i,j,x,tmp:longint; begin
 i:=l; j:=r; x:=a[(i+j) div 2];  repeat
  while a[i]<x do inc(i);   while a[j]>x do dec(j);   if i<=j then
   begin
    if i<>j then
     begin
      tmp:=a[i];
      a[i]:=a[j];
      a[j]:=tmp;      end;
    inc(i);
    dec(j);    end;  until i>j;  if l<j then qsort(a,l,j);  if i<r then qsort(a,i,r);end;begin
readln(w);
readln(n); for i:=1 to n do
 readln(a[i]);
qsort(a,1,n);
i:=n; j:=1; while i>=j do
 begin
  if a[i]+a[j]<=w then//可以放两个
   begin
    dec(i);
    inc(j);    end
   else dec(i);//不能放两个
  inc(count);//计数器加一
 end;
writeln(count);end.

评论

还没有评论

评论

作者: liuliming6772 更新时间: 2017-10-08 09:00  在Ta的博客查看  1 

这道题是一个贪心题，看楼下的各位大佬、大神们，在用桶排和标记来写，蒟蒻在万分景仰膜拜之余，也深感难以理解，所以发下自己的思路。

读入之后先用sort排序，然后用两个指针一起向中间走，每次选择都尽可能的让当前状态下最大的和最小的分在一组，如果不行就最大的单独分一组，这样贪心下来就是最少分的组了。证明如下：

如果最大的a[r]不与最小的a[l]分在一组，而是a[r]与a[i]在一组,a[l]与a[j]在一组，因为a[l]<=a[i]&&a[r]>=a[j],所以交换两者分组不影响后续选择，而a[r]如果不能与a[l]在一组，因为a[l]为当前最小值，所以a[r]只能单独为一组，所以贪心是 正确的。

#include<bits/stdc++.h>using namespace std;int W,ans=0;int n,a[30001];int l,r,i;int main(){    scanf("%d%d",&W,&n);    for(i=1;i<=n;i++)      scanf("%d",&a[i]);
   sort(a+1,a+n+1);
   l=1;  r=n;    while(l<=r)//一定要有等号。
   {        if(a[l]+a[r]<=W)   //一定要有等号。
         l++,r--,ans++;        else
         r--,ans++;   //贪心过程
   }    printf("%d",ans);    return 0;
}

评论

chengdadao
算法速度快，落谷能过。但i>=5，j>=5貌似有点问题。 100 3 90 3 3 的数据好像是错误结果。

评论

作者: 你好帅_56 更新时间: 2017-10-02 20:04  在Ta的博客查看  0 

在此放一个比较简洁易懂的桶排序，因为每组最多只能包括两件纪念品，所以其实模拟一下发现无需排序，同时我们发现w范围很小，因此桶排序还能缩小循环范围。

#include<iostream>#include<cstdio>#include<algorithm>using namespace std;int x,n,w,p[201],num;int main(){    cin>>w>>n;    for(int i=1;i<=n;i++)
   {        scanf("%d",&x);
       p[x]++;
   }    for(int i=200;i>=5;i--)
   {        while(p[i])
       {
           num++;
           p[i]--;            for(int j=w-i;j>=5;j--)//贪心，找到能装的最大的放进来；
           {                if(p[j])
               {
                   p[j]--;                    break;//只能装2个；
               }
           }
       }
   }    cout<<num<<endl;    return 0;
}