Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

大佬帮忙看看 n^2logn为什么超时

Posted by hulian425 at 2019-09-14 20:46:49 on Problem 2549
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator