题解：ABC321D - Set Menu

题解：ABC321D - Set Menu

·题目

链接：Atcoder。

链接：洛谷。

·难度

算法难度：B。

思维难度：C。

调码难度：B。

综合评价：见洛谷链接。

·算法

枚举+二分查找。

·思路

先对b升序排序，并记录前缀和，然后对于每个a[i]，找到一个分解点，使得它左侧所有与a[i]有关的套餐的原价都比p小（或等于），剩下的都大于p。那么端点左侧的采用原价购买，（l表示分界点左侧）即s[l]+a[i]*l，右侧的就采用p价格购买，花费p*(m-l)。累加每个a[i]即可。

·代价

O((n+m)*log(m))，其中O(m*log(m))是排序，O(n*log(m))是二分查找，也就是程序核心。

·细节

升序排序用sort。

·代码

#include<bits/stdc++.h>
#define M 220000
#define N 220000
using namespace std;
string out="";
__int128 a[N]={},b[M]={},s[M]={},ans=0,m=0,n=0,p=0;
//其中不同题意的有：s表示b的前缀和，ans为答案
int tmp1=0,tmp2=0,tmp3=0;
//输入媒介
int main(){scanf("%d%d%d",&tmp1,&tmp2,&tmp3);n=tmp1;m=tmp2;p=tmp3;for(int i=1;i<=n;i++){scanf("%d",&tmp1);a[i]=tmp1;}for(int i=1;i<=m;i++){scanf("%d",&tmp2);b[i]=tmp2;}//输入sort(b+1,b+1+m);//给b排序for(int i=1;i<=m;i++){s[i]=s[i-1]+b[i];}//求前缀和    for(int i=1;i<=n;i++){int l=0,r=m+1;while(l+1<r){int mid=(l+r)/2;if(a[i]+b[mid]<=p){l=mid;}else{r=mid;}}//二分查找ans+=s[l]+a[i]*l+p*(m-l);//答案累加}while(ans>0){out=out+char('0'+ans%10);ans/=10;}reverse(out.begin(),out.end());printf("%s\n",out.c_str());//输出答案return 0;
}

·注意

long long都不行，要用__int128。