Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
大佬帮忙看看 n^2logn为什么超时#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<vector> #include<map> #define NN printf("\n") #define pri(x) printf("%d", x) #define scc(x) scanf("%c", &x) #define sci(x) scanf("%d", &x) #define prc(x) printf("%c", x) using namespace std; typedef long long ll; int n; int a[1003]; struct subb { int v; int a; int b; }; bool cmp(subb a, subb b) { return a.v < b.v; } int nn; void solve() { // 输入 int i = 0; for (; i < n; i++) { sci(a[i]); } // 求和枚举 vector<subb> sub; map<int, pair<int, int> > add; //map<int, pair<int, int> > sub; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { add[a[i] + a[j]] = make_pair(a[i], a[j]); } } // 做差枚举 for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { subb tep; tep.v = a[i] - a[j]; tep.a = a[i]; tep.b = a[j]; sub.push_back(tep); tep.v = a[j] - a[i]; tep.a = a[j]; tep.b = a[i]; sub.push_back(tep); } } sort(sub.begin(), sub.end(), cmp); nn = sub.size(); map<int, pair<int, int> >::iterator p, q; int maxn = -1; for (q = add.begin(); q != add.end(); q++) { int t = q->first; // 二分搜索 int l = 0, r = nn; while (r - l > 1) { int mid = (r + l) / 2; if (t < sub[mid].v) { r = mid; } else l = mid; } if (sub[l].v == t) { if (q->second.first != sub[l].a && q->second.first != sub[l].b && q->second.second != sub[l].a && q->second.second != sub[l].b) { if ((q->first + sub[l].b) > maxn) { maxn = (q->first + sub[l].b); } } } } if (maxn > 0) printf("%d\n", maxn); else printf("no solution\n"); return ; } int main() { while (sci(n) && n) { solve(); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator