本文主要是介绍10125-Sumsets【暴力】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
利用n^2的时间枚举所有a[i] + a[j]
利用n^2的时间枚举所有a[i] - a[j]
之后利用n^2时间一个一个找a[i] - a[j]的值是否存在于a[i] + a[j]中
找的时候需要二分查找
另外一点就是注意long long的范围以及四个数是集合内不同的四个元素
| 15222638 | 10125 | Sumsets | Accepted | C++ | 0.449 | 2015-03-26 15:40:29 |
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 1005;
struct St{LL v;int x,y;St(LL v,int x,int y):v(v),x(x),y(y){};
};
int n,ok;
LL ans;
LL array[maxn];
vector<St>arr;
vector<St>arr2;
void debug(){for(int i = 0; i < arr.size(); i++)printf("%I64d ",arr[i].v);puts("");for(int i = 0; i < arr2.size(); i++)printf("%I64d ",arr2[i].v);puts("");
}
bool cmp1(St a,St b){return a.v < b.v;
}
bool cmp2(St a,St b){return a.v > b.v;
}
bool solve(LL v,int x,int y){int l = 0, r = arr.size() - 1;while(l < r){int mid = l + (r - l) / 2;//printf("%I64d %d %d %d %I64d\n",arr[mid].v,l,r,mid,v);if(arr[mid].v >= v)r = mid;elsel = mid + 1;}for(int i = l; i < arr.size(); i++){if(arr[i].v != v) break;int xx = arr[i].x,yy = arr[i].y;if(xx != x && xx != y && yy != x && yy != y){if(!ok)ans = arr[i].v + array[y];elseans = max(ans,arr[i].v + array[y]);return true;}}return false;
}
int main(){while(scanf("%d",&n) && n){arr.clear();arr2.clear();for(int i = 0; i < n; i++)scanf("%lld",&array[i]);for(int i = 0; i < n; i++)for(int j = i + 1; j < n; j++)arr.push_back(St(array[i] + array[j],i,j));for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)if(i != j)arr2.push_back(St(array[i] - array[j],i,j));sort(arr.begin(),arr.end(),cmp1);sort(arr2.begin(),arr2.end(),cmp2);//debug();ok = 0;for(int i = 0; i < arr2.size(); i++){LL v = arr2[i].v;int x = arr2[i].x,y = arr2[i].y;if(solve(v,x,y)){ok = 1;}}if(ok)printf("%lld\n",ans);elseprintf("no solution\n");}return 0;
}
这篇关于10125-Sumsets【暴力】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
