cf1379c---贪心+思维

题目链接：https://codeforces.com/contest/1379/problem/C

题意：有m种花，买第1朵的价值为ai，以后再买的价值为bi。现在可以买n朵，求最大价值

容易看出（划掉），对于一种最优的方案，只可能在一种花里买bi的部分。这样就可以枚举在哪种花里买bi的部分，同时算出对于这种bi，有多少个ai比它大，之后把这些bi换成买ai即可。枚举的时间复杂度是O(m)，求有多少个ai比bi大可以先排序再用upper_bound，是O(logm)的，总时间复杂度O(mlogm)。关于枚举bi的过程，我认为有一些细节要想清楚。首先假如有>=n个ai比它大，那么就直接取这n个就可以了（当前的bi取0个）。否则有两种情况：取完比bi大的那些ai，再取当前的ai，剩下的全部取当前的bi;或者直接取最大的n个ai（如果m>=n），两种情况取max即可

#include<bits/stdc++.h>
#define ll long long
using namespace std;
 
const int M=1e5+10;
struct st{ll a,b;}x[M];
ll n,m,i,t,c[M],pre[M];
 
bool cmp(st p,st q){return p.a<q.a;}
 
int main(){
	std::ios::sync_with_stdio(false);
	cin>>t; pre[0]=0;
	while (t--){
	  cin>>n>>m;
	  for (i=1;i<=m;i++) cin>>x[i].a>>x[i].b;
	  sort(x+1,x+m+1,cmp);
	  for (i=1;i<=m;i++) c[i]=x[i].a; c[m+1]=1e10;
	  for (i=1;i<=m;i++) pre[i]=pre[i-1]+c[i];
	  ll ans=0;
	  for (i=1;i<=m;i++){ //枚举每个bi 
	  	ll res=0;
	  	ll pos=upper_bound(c+1,c+m+1,x[i].b)-c;
	  	ll num=m-pos+1; //有多少个ai比bi大 
	  	if (num<=n-1) {
		  res+=(pre[m]-pre[pos-1]+(n-1-num)*x[i].b+x[i].a);
		  if (x[i].a>=x[i].b) res+=(x[i].b-x[i].a);
		  if (m>=n) res=max(res,pre[m]-pre[m-n]);
	    }
	    else res=pre[m]-pre[m-n];
	  	ans=max(ans,res);
	  }
	  cout<<ans<<endl; 
	}
	return 0;
}