锐客网

  1. 首页 > it技术 > >

#|C. Choosing flowers（枚举+思维+二分）

#思维cf

原题链接： https://codeforces.com/problemset/problem/1379/C
#|C. Choosing flowers（枚举+思维+二分）
文章图片

测试样例：

Input
2
4 3
5 0
1 4
2 2
5 3
5 2
4 2
3 1
Output
14
16
样例解释：
In the first example case Vladimir can pick 1 flower of the first type and 3 flowers of the second type, in this case the total happiness equals 5+(1+2?4)=14.
In the second example Vladimir can pick 2 flowers of the first type, 2 flowers of the second type, and 1 flower of the third type, in this case the total happiness equals (5+1?2)+(4+1?2)+3=16.
题意： 给定 m m m种鲜花的信息：购买第 i i i种花 x i x_i xi?朵所得的价值为 a i + ( x i ? 1 ) ? b i a_i+(x_i-1)*b_i ai?+(xi??1)?bi?，问你购买 n n n朵鲜花所获得的最大价值。
解题思路： 我们先来分析一下这道题目，总共有m种花，我们如果买一朵得到的价值就是 a i a_i ai?，那么不会考虑到 b i b_i bi?。如果我们这朵花我们之前买过，则我们获得的价值就为 b i b_i bi?，那么我们可以推断一下，我们购买的最优方案花的数量大于1的花只有一种。因为如果你购买的超过两种，那么我们完全可以选择那个 b i b_i bi?值比较大的进行操作。所以我们可知我们的购买方案花的数量大于1的只有一种。OK，那么我们就可以枚举我们所购买的数量大于1的那一种花。然后对于此花，我们的最优购买方案是先把其他花价值 a i a_i ai?大于这个 b b b的都买掉，最后再全部购买 b b b，这就是最优方案。那么，我们要取所有枚举结果的最大值即可。具体看代码。
【#|C. Choosing flowers（枚举+思维+二分）】AC代码：
/* *注：文章若有任何问题请私信我或评论区留言，谢谢支持。 *blog:https://me.csdn.net/hzf0701 *邮箱：unique_powerhouse@qq.com * */ #include //POJ不支持#define rep(i,a,n) for (int i=a; i<=n; i++)//i为循环变量，a为初始值，n为界限值，递增 #define per(i,a,n) for (int i=a; i>=n; i--)//i为循环变量， a为初始值，n为界限值，递减。 #define pb push_back #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define fi first #define se second #define mp make_pairusing namespace std; const int inf = 0x3f3f3f3f; //无穷大 const int maxn = 1e5+2; //最大值。 typedef long long ll; typedef long double ld; typedef pairpll; typedef pair pii; //*******************************分割线，以上为自定义代码模板***************************************//int t,n,m; struct node{ ll a,b; }nums[maxn]; ll c[maxn],sum[maxn]; int main(){ //freopen("in.txt", "r", stdin); //提交的时候要注释掉 IOS; while(cin>>t){ while(t--){ cin>>n>>m; rep(i,1,m){ cin>>nums[i].a>>nums[i].b; c[i]=nums[i].a; } sort(c+1,c+1+m); sum[0]=0; rep(i,1,m){ sum[i]=sum[i-1]+c[i]; } ll ans=0,temp,pos,len,q; rep(i,1,m){ temp=0; q=n; pos=lower_bound(c+1,c+1+m,nums[i].b)-c; len=min(q,m-pos+1); //获取我们要买的数目。 temp+=sum[m]-sum[m-len]; q-=len; if(q>0){ if(c[pos]>nums[i].a||pos==m+1){ temp+=nums[i].a; q--; } temp+=nums[i].b*q; } ans=max(ans,temp); } cout<

    推荐阅读


    上一篇：读经感恩日志87

    下一篇：道歉不仅仅是“对不起！”