首页 > 代码库 > [hihoCoder]1514_偶像的条件
[hihoCoder]1514_偶像的条件
链接:https://hihocoder.com/problemset/problem/1514
题意:偶像的条件
给定三个数组A,B,C,从中各挑出一个数a,b,c,使得D=|a-b|+|b-c|+|c-a|最小,输出最小的D
题解:
不那么水的水题 ( 啪 x )
考虑一下数学,给x,y,z,不妨设 x>y>z,那么
D=|x-y|+|y-z|+|z-x|=(|x-y|+|y-z|)+|x-z|=(x-y+y-z)+|x-z|= 2 * | x - z |
实际上就变成了在这三个数组找出一个最大值,剩余两个数组中找出一个最小值,然后最后一个数组里必须有元素位于最大值与最小值之间,想办法使得找到的最大值和最小值尽可能小就好了
那么就枚举好了,假设挑出的元素按照大小顺序,他们所属的集合可能是 ABC ACB BAC BCA CAB CBA
用min表示最小的那个结果(初始化为无穷)
对第一个:枚举A中的所有值作为最大值,比如a,通过在C中枚举所有小于等于a的值作为最小值,然后查找看看B中存不存在 b 使得 c<=b<=a,如果有,而且a-c<min,那么更新min就好了
剩下的也类似
比较方便的查找的方法(有序情况下)可以考虑使用二分查找,时间复杂度是O(logN)的,快得一批
#include<cstdio> #include<cmath> #include<cctype> #include<cstring> #include<iostream> #include<string> #include<sstream> //stringstream ss(line) #include<algorithm> //sort(a,a+n,cmp) //p=lower_bound(a,a+n,x)-a+1(大于或等于x的第一个位置) #include<vector> #include<bitset> //bitset<N> xx using namespace std; const int U=3; const int INF = 1e8; vector<int> save[U]; int LEN[U]; void print(){ for(int i=0;i<U;i++){ printf("\n*******\n"); for(int j=0;j<LEN[i];j++){ printf("%d ",save[i][j]); } } return ; } int main(){ for(int i=0;i<U;i++) scanf("%d",LEN+i); int d,d1,d2,d3; vector<int>::iterator pos; for(int i=0;i<U;i++){ for(int j=0;j<LEN[i];j++){ scanf("%d",&d); //pos = lower_bound(save[i].begin(),save[i].end(),d); //save[i].insert(pos,d); save[i].push_back(d); } sort(save[i].begin(),save[i].end()); } //print(); int min = INF; for(int i=0;i<U;i++){ //max for(int j=0;j<U;j++){ //min if(j==i) continue; int k=3-i-j; for(int ii=LEN[i]-1;ii>=0;ii--){ d1 = save[i][ii]; int jj = lower_bound(save[j].begin(),save[j].end(),d1-min)-save[j].begin(); int jjj = lower_bound(save[j].begin(),save[j].end(),d1)-save[j].begin(); for(;jj<=jjj;jj++){ d2 = save[j][jj]; if(d2>d1) continue; d = lower_bound(save[k].begin(),save[k].end(),d2) - save[k].begin(); d3 = save[k][d]; if(d3<=d1&&d3>=d2){ if(min>d1-d2){ //printf("i=%d,j=%d,d1=%d,d2=%d,d3=%d\n",i,j,d1,d2,save[k][d]); min = d1-d2; } } } } } } printf("%d",min*2); return 0; }
其实本来一开始想用线段树维护的,不过自从发现CF找中间值那道题可以用vector+lower_bound()来做之后现在都不怎么想宠幸线段树了=_=想想还是用二分吧。。
[hihoCoder]1514_偶像的条件
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。