当前位置: 代码迷 >> 综合 >> HAUT OJ 1231: ykc买零食
  详细解决方案

HAUT OJ 1231: ykc买零食

热度:85   发布时间:2023-12-04 03:34:57.0


问题描述:

ykc的班级准备举行班级聚会,而身为生活委员的ykc要为此准备好零食,这天,ykc来到了学校的新起点超市,在转了3个小时候,ykc决定买以下所有的n种零食,其中每种零食的价格可能不一样,而刚好超市有活动,每买m种零食,就可以任选一种不超过k元的零食并免费赠送,而ykc想尽可能的省钱,求ykc的最小花费

输入:

输入包含多组数据,以EOF结束,

每组首先输入三个正整数,n,m,k,其中(n,m,k<100)

后输入n个数表示每种零食的价格ai(ai<1000)

输出:

输出一个正整数,表示最小花费

样例输入:

4 3 2
1 2 3 4
7 3 8
1 2 3 4 5 6 7

样例输出:

8
21





原因分析:

1. 计算免单个数时 应该n/m+1   而不是 n/m   举个例子:免单条件是买够3件   你若买3件,则没有可以免的,只有买4件才能免一件  

2.循环变量第一次忘了初始化,后来才发现;

3.减去免单的金额时,忘了标记被免单过的商品,导致第二次重复免单,出现错误





解决方案:


#include<stdio.h>
#include<math.h>
int cmp(const void*a,const void*b)
{return (*(int*)b - *(int*)a);
}
int main()
{int n,m,k,s=0,i,p,j,f;while(scanf("%d%d%d",&n,&m,&k)!=EOF){int a[102]={0};   //多实例一定要注意循环变量的初始s=0;f=-1;for(i=0;i<n;i++){scanf("%d",&a[i]);   s+=a[i];}qsort(a,n,sizeof(int),cmp);p=n/(m+1)==0?0:n/(m+1);   //不能写成 n/m  要把免单的一个也算进mif(p<=0)printf("%d\n",s);else{for(i=0;i<n;i++)if(a[i]<=k){f=i;     //找到小于免单金额的那个位置break;}if(f!=-1){for(j=1;j<=p;j++)  // j记录免单次数for(i=f;i<n;i++){if(a[i]!=-1){s-=a[i];a[i]=-1; //第二个for每次都要从f重新开始,所以要避免重复减去免单的商品break;   //减一次就要退出循环}}}printf("%d\n",s);}}return 0;
}