| ||||||||||
| 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