CodeForces - 1379C - Choosing flowers 二分

CodeForces - 1379C - Choosing flowers 二分

题意：给出 $m$种商品，购买 $x$次该商品 $i$获得的利润是:
$val(x)= \begin{cases} 0& \text{x=0}\\ a_i+(x-1)*b_i& \text{x!=0} \end{cases}$

思路：只可能会取到一个 $b_i$，换句话说，最多只有一种商品会被购买多次

证明：

假设在某一次购买时第i个商品第二次被购买说明该抉择是m个抉择中最优的，故第二次购买它购买之后，所有的状态并没有发生改变(由于商品数量是无限的)故下一个抉择仍然选择第i个商品
证毕

做法：枚举允许被重复购买多次的商品 $i$，二分找到比 $b[i]$大的所有 $a[i]$，注意该位置如果 $>i$，则还得把第i个商品的第一次给购买

代码：

int t,n,m,a[maxn];
ll sum[maxn],cnt;
struct node
{int a,b;
}p[maxn];
bool cmp(node a,node b){return a.a<b.a;}
int main()
{scanf("%d",&t);while(t--){ll ans=0;scanf("%d%d",&n,&m);rep(i,1,m)scanf("%d%d",&p[i].a,&p[i].b);sort(p+1,p+1+m,cmp);rep(i,1,m)a[i]=p[i].a,sum[i]=sum[i-1]+a[i];rep(i,1,m){int pos=distance(a,upper_bound(a+1,a+1+m,p[i].b));if (pos>m){cnt=a[i];cnt+=1ll*(n-1)*p[i].b;}else{if (pos>i){cnt=a[i];int cutnum=min(m-pos+1,n-1);//[m-cutnum+1,m]cnt+=sum[m]-sum[m-cutnum];cnt+=1ll*(n-1-cutnum)*p[i].b;}else if (pos<=i){cnt=0;int cutnum=min(m-pos+1,n);//[m-cutnum+1,m]cnt+=sum[m]-sum[m-cutnum];cnt+=1ll*(n-cutnum)*p[i].b;}}ans=max(ans,cnt);}WW(ans);}return 0;
}