No.165 - Codeforces-Contest-1282

No.165 - Codeforces-Contest-1282 - B

阅读量：4057 次

发布时间：2019-05-25

本文共 1356 字，大约阅读时间需要 4 分钟。

n个物品，每个物品对应价格。

有种优惠，买物品A可以附赠价值小于A的k-1件商品

则，现有p数量钱，最多买几件物品？

原问题：优惠必须选k-1件赠品，多和少都不可以

思路：k间隔枚举，再在从小价值物品里面挑

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;#define maxn 200005int num[maxn];int main(){
       int T;    scanf("%d",&T);    while(T--){
           int n,p,k;        scanf("%d%d%d",&n,&p,&k);        for(int i=0;i
       
        =num[j]){
                       sum -= num[j];                    cnt += k;                }else{
                       break;                }            }            for(int j=0;j
        
         = num[j]){ sum -= num[j]; cnt++; }else{ break; } } ans = max(ans,cnt); } printf("%d\n",ans); } return 0;}

进阶问题：优惠可以选0～k-1件赠品

思路：0～k-1开始k间隔枚举

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;#define maxn 200005int num[maxn];int main(){
       int T;    scanf("%d",&T);    while(T--){
           int n,p,k;        scanf("%d%d%d",&n,&p,&k);        for(int i=0;i
       
        = num[j]){
                       sum-=num[j];                    cnt = max(cnt,j+1);                }else{
                       ans = max(ans,cnt);                    flag = false;                    break;                }            }            if(flag) ans = max(ans,cnt);        }        printf("%d\n",ans);    }    return 0;}