题解 CF810B 【Summer sell-off】

这题居然没有题解，小蒟蒻就来发一篇吧。

---

首先，我们要分析：根据题目，每天有 (l_i) 名顾客和 (k_i) 个商品，
既然保证再商品足够的情况下，每名顾客买且只买一件商品，那就不难得出：第 (i) 天可卖 (min(l_i,k_i)) 件商品。

又有 (f) 天的商品数量翻倍，那么再这些天里，第 (i) 天可卖 (min(l_i,k_i imes2)) 件商品。

那么，如果想将利益最大化，选择的 (f) 天就要将 (min(l_i,k_i imes2)-min(l_i,k_i)) 做到最大。增加的数量多，总的数量就多啦。

简单分析后，就可以发现其实这题就是一个简单的贪心，将所有天的差值算出来，由大到小排个序，选择前面的 (f) 天，利益就最大了。

---

好了，泥萌最喜欢的完整 AC 代码：

#include<bits/stdc++.h>
#define ull unsigned long long
#define rg register
using namespace std;
struct node      //结构体来存储人数和价值。 
{
	ull k,l;
}a[200005];

ull n,f,ans;
bool cmp(node x,node y)    //这个是 sort 将要用到的比较函数。 
{                          //这个函数就可以按照 min(li,ki*2) - min(li,ki) 由大到小排序。 
	return (min(x.k*2,x.l)-min(x.k,x.l))>(min(y.k*2,y.l)-min(y.k,y.l));
}
int main()
{
	cin>>n>>f;
	for(rg int i=0;i<n;i++)
		cin>>a[i].k>>a[i].l;    //读入部分。 
		
	sort(&a[0],&a[n],cmp);      //排序，STL 大法好。 
	for(rg int i=0;i<f;i++)
		a[i].k=a[i].k*2;        //找到前 f 天，将数量翻倍。 	
	for(rg int i=0;i<n;i++)
		ans+=min(a[i].k,a[i].l);   //计算选择后的商品售卖数量。
		 
	cout<<ans<<endl;           //输出。 
	return 0;
}

小蒟蒻写题解也不容易啦。