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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

贴份c++暴搜AC代码,要找到合适的搜索方式

Posted by a280920481 at 2018-11-19 22:17:07 on Problem 2718
//此方法对于位数为偶数的情况会做额外的一倍运算次数,可考虑使用另外的 flag 对偶数情况进行处理,防止重复搜索对称的情况

#include <iostream>
using namespace std;


int ans, len1, len2;
bool flag[10];

void getresult1(int length, int q);
void getresult2(int length, int &q, int a);


int main()
{
	int n, len;
	char c[50];

	cin >> n;
	cin.get();

	for (int so = 0; so < n; so++)
	{
		for (int i = 0; i < 10; i++)
		{
			flag[i] = false;
		}
		ans = 2 << 29;//先将 ans 设为一个足够大的数
		len = 0;

		cin.getline(c, 50);

		for (int i = 0; i < 50; i++)
		{
			if ((c[i] >= 48) && (c[i] <= 57))
			{
				flag[c[i] - 48] = true;
				len++;
			}
			if (!c[i])
			{
				break;
			}
		}

		//结果一定是位数相同或相差一位的两个数的差

		len1 = len >> 1;//让第一个数的位数不大于第二个数,以减少对 0 的判断次数
		len2 = len - len1;

		getresult1(0, 0);

		cout << ans << '\n';
	}
	return 0;
}

void getresult1(int length, int q)
{
	if (length == len1)
	{
		getresult2(0, q, 0);
	}
	else
	{
		int i = 0;
		if ((!length) && (len1 > 1))
		{
			i = 1;
		}
		for (; i < 10; i++)
		{
			if (flag[i])
			{
				flag[i] = false;
				getresult1(length + 1, q * 10 + i);
				flag[i] = true;
			}
		}
	}
	return;
}

void getresult2(int length, int &q, int a)
{
	if (length == len2)
	{
		if (a > q)//分正负
		{
			if ((a - q) < ans)
			{
				ans = a - q;
			}
		}
		else
		{
			if ((q - a) < ans)
			{
				ans = q - a;
			}
		}
	}
	else
	{
		int i = 0;
		if (!length)
		{
			i = 1;
		}
		for (; i < 10; i++)
		{
			if (flag[i])
			{
				flag[i] = false;
				getresult2(length + 1, q, a * 10 + i);
				flag[i] = true;
			}
		}
	}
	return;
}

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