链接：https://codeforces.com/contest/1379/problem/C
题意：弗拉基米尔想为他的妻子准备一份礼物：他决定给买整整n朵花。弗拉基米尔去了一家花店， 那里有m种花卉出售，每种类型的花卉供应无限。他知道在收到第i种类型的第一朵花后，他的妻子的幸福感增加了ai，在收到每一朵连续的这种类型的花之后，她的幸福感增加了bi。也就是说，如果在所选的i花中有xi朵，他的妻子得到Ai+（Xi-1）Bi的额外幸福（如果没有I型花，她就不会得到这种类型的花）。 请帮助弗拉基米尔挑选n朵鲜花，使他妻子的幸福感最大化.
思路：假设达到最优，其中所取的b[i]必然相同的花或根本没取b[i]。枚举每一种a[i]，先取a[i]，再取所有比b[i]大的a[]，再取剩余该取的b[i]。每次枚举都更新答案，最后得到最优解。
（我不太会二分）
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 1e9 + 7; const int N = 1e5 + 5; ll a[N],b[N],c[N],sum[N]; ll n,m; bool cmp(ll x,ll y){ return x>y; } ll find(ll x){ ll l=0,r=m-1,ans=m; while(l<=r){ ll mid=(l+r)>>1; if(c[mid]<=x) r=mid-1,ans=mid; else l=mid+1; } return ans-1; } int main(){ int t;cin>>t; while(t--){ cin>>n>>m; for(ll i=0;i<m;i++){ cin>>a[i]>>b[i]; c[i]=a[i]; } sort(c,c+m,cmp); sum[0]=c[0]; for(int i=1;i<m;i++){ sum[i]=sum[i-1]+c[i]; } ll ans=0,ans1=0; for(ll i=0;i<m;i++){ ll j=find(b[i]); if(a[i]>=b[i]){ ans1=sum[min(j,n-1)]+b[i]*max((n-j-1),ll(0)); } else{ ans1=sum[min(j,n-2)]+a[i]+b[i]*max((n-j-2),ll(0)); } ans=max(ans,ans1); } cout<<ans<<endl<<endl; } return 0; }
原文：https://www.cnblogs.com/asunayi/p/13360750.html