当前位置: 代码迷 >> 综合 >> Codeforces1379 C. Choosing flowers(贪心+二分)
  详细解决方案

Codeforces1379 C. Choosing flowers(贪心+二分)

热度:26   发布时间:2024-01-31 22:48:13.0

题意:

有m种花,每种的数量无限,每朵花有a(i)和b(i)。
现在你需要挑出n朵花,第一次挑选某种花的时候,权值增加a(i),之后每次都只增加b(i)
问挑选n朵花能得到的最大权值是多少。

数据范围:m<=1e5,n<=1e9

解法:

如果某种花要购买多次,那么之后每次增加的权值是b(i),
一种想法是选出b(i)最大的,如果买超过一朵就都买这种花,
贪心一下,买这个b(i)之前,把所有大于这个b(i)的其他a(i)都买下来。

但是这种做法有一个问题,就是最大的b(i)本身对应的a(i)可能很小,
例如:
2 2
11 9
1 10
这组数据第二种花的b(i)很大,但是a(i)很小,就不成立了。

但是从上面的想法可以推测出,最多只有一种花买超过一朵,
那么枚举这个超过一朵的花,优先买大于b(i)的其他a(i)花,然后剩下的全买这种就行了,对答案取max
找大于b(i)的花可以用排序+二分做

需要注意的点:
如果a(i)>b(i),那么买大于b(i)的花的时候已经买了当前a(i)
如果a(i)<=b(i),那么还需要多花费一次机会买当前a(i)

code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxm=1e5+5;
struct Node{int a,b;
}a[maxm];
int sum[maxm];
int c[maxm];
int n,m;
bool cmp(int a,int b){return a>b;
}
signed main(){int T;cin>>T;while(T--){cin>>n>>m;for(int i=1;i<=m;i++){cin>>a[i].a>>a[i].b;c[i]=a[i].a;}sort(c+1,c+1+m,cmp);//从大到小排序for(int i=1;i<=m;i++){sum[i]=sum[i-1]+c[i];}int ans=0;for(int i=1;i<=m;i++){//枚举最后b[i]买的是哪种int temp=0;int remain=n;//二分找>b[i]的int l=1,r=m;int p=-1;while(l<=r){int mid=(l+r)/2;if(c[mid]>a[i].b){p=mid,l=mid+1;}else{r=mid-1;}}if(p==-1){//没有>b[i]的,那么全买这一种ans=max(ans,a[i].a+(n-1)*a[i].b);continue;}//if(p>n)p=n;temp+=sum[p];remain-=p;if(a[i].a>=c[p]){temp+=a[i].b*remain;}else{if(remain){temp+=a[i].a;remain--;temp+=a[i].b*remain;}}//ans=max(ans,temp);}cout<<ans<<endl;}return 0;
}