广州o2o网站建设,网络规划设计师视频百度网盘,桂城网站设计,邯郸网站建设行情题解#xff1a;ABC321D - Set Menu
题目
链接#xff1a;Atcoder。
链接#xff1a;洛谷。
难度
算法难度#xff1a;B。
思维难度#xff1a;C。
调码难度#xff1a;B。
综合评价#xff1a;见洛谷链接。
算法
枚举二分查找。
思路
先对b升序排序#x…题解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((nm)*log(m))其中O(m*log(m))是排序O(n*log(m))是二分查找也就是程序核心。
·细节
升序排序用sort。
·代码
#includebits/stdc.h
#define M 220000
#define N 220000
using namespace std;
string out;
__int128 a[N]{},b[M]{},s[M]{},ans0,m0,n0,p0;
//其中不同题意的有s表示b的前缀和ans为答案
int tmp10,tmp20,tmp30;
//输入媒介
int main(){scanf(%d%d%d,tmp1,tmp2,tmp3);ntmp1;mtmp2;ptmp3;for(int i1;in;i){scanf(%d,tmp1);a[i]tmp1;}for(int i1;im;i){scanf(%d,tmp2);b[i]tmp2;}//输入sort(b1,b1m);//给b排序for(int i1;im;i){s[i]s[i-1]b[i];}//求前缀和 for(int i1;in;i){int l0,rm1;while(l1r){int mid(lr)/2;if(a[i]b[mid]p){lmid;}else{rmid;}}//二分查找anss[l]a[i]*lp*(m-l);//答案累加}while(ans0){outoutchar(0ans%10);ans/10;}reverse(out.begin(),out.end());printf(%s\n,out.c_str());//输出答案return 0;
}
·注意
long long都不行要用__int128。
