天梯题集——秀恩爱分得快（实现与讨论）

前言

本文分为两个部分：实现、讨论。其中讨论部分表现出对计算机原理的思考…

秀恩爱分得快

---

该题并不是很难，只要会运用数组就能够实现，但如何用更简单的方式实现是值得我们深思的问题…

实现

下面是我借鉴 其他博主 改善的代码

#include<bits/stdc++.h>
using namespace std;

double gx[1010][1010];
bool sex[1010];			//bool类型更快于int类型，位数更少 

int read(){
	int num=0, flag=0;	//flag不可用bool类型，会超时 
	char a=getchar();
	
	while((a<'0'||a>'9')&&a!='-')
		a=getchar();
	while(a=='-'||(a>='0'&&a<='9')){
		if(a=='-') 
			flag=1;
		else
			num = num*10 + a-'0';
		a = getchar();
	}
	sex[num] = flag;
	return num;
}

void print(int a, int b){
	if(sex[a])
		printf("-");
	printf("%d ", a);
	if(sex[b])
		printf("-");
	printf("%d\n", b);
	return;
}

int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	while(m--){
		int wumen[1010], men[1010];
		int tmp, index_w=0, index_m=0;
		scanf("%d", &tmp);
		double k=tmp;
		while(tmp--){
			int num = read();
			if(sex[num])
				wumen[index_w++] = num;
			else
				men[index_m++] = num;
		}
		
		for(int i=0; i<index_m; i++)
		for(int j=0; j<index_w; j++){
			gx[men[i]][wumen[j]] += 1/k;	//多次进行强制类型转换 
			gx[wumen[j]][men[i]] += 1/k;	//会明显地增加耗时 
		}
	}
	
	int a = read(), pa = read();
	double max1=0,max2=0;
	for(int i=0; i<n; i++){
		max1 = max(gx[a][i], max1);
		max2 = max(gx[pa][i], max2);
	}
	
	//double值不能直接比较，对吧？
	if(fabs(max1-gx[a][pa])<1e-17 && fabs(max2-gx[pa][a])<1e-17){
		print(a, pa);
	}
	else{
		for(int i=0; i<n; i++)
		if(fabs(max1-gx[a][i])<1e-17)
			print(a, i);
		for(int i=0; i<n; i++)
		if(fabs(max2-gx[pa][i])<1e-17)
			print(pa, i);
	}
	
	return 0;
} 

为什么 flag 有 bool 类型就会出现超时？？？

---

讨论

讨论形式是对其他博主的代码进行思考->其他博主
（该博主的代码也能够AC的）
①、该博主的解题代码

#include <bits/stdc++.h>
using namespace std;
 
double friends[1000][1000];
bool sex[1000];//0--man   1--woman
 
int Read()
{
	bool flag = 0;
	char a = getchar();
	int ans = 0;
	while ((a<'0' || a>'9') && a != '-')
	{
		a = getchar();
	}
	while (a == '-' || a >= '0'&&a <= '9')
	{
		if (a == '-')flag = 1;
		else
		{
			ans = ans * 10 + a - '0';
		}
		a = getchar();
	}
	sex[ans] = flag;
	return ans;
}
 
void Print(int a, int b)
{
	if (sex[a])cout << '-';
	cout << a << ' ';
	if (sex[b])cout << '-';
	cout << b << endl;
}
 
int main()
{
	int popu, picture;
	cin >> popu >> picture;
	while (picture--)
	{
		vector <int> gender[2];//0--man   1--woman
		int poto_popu;
		cin >> poto_popu;
		double cnt = poto_popu;
		while (poto_popu--)
		{
			int number = Read();
			gender[sex[number]].push_back(number);
		}
		for (int i = 0; i<gender[0].size(); i++)
		{
			for (int j = 0; j<gender[1].size(); j++)
			{
				friends[gender[0][i]][gender[1][j]] += 1 / cnt;
				friends[gender[1][j]][gender[0][i]] += 1 / cnt;
			}
		}
	}
 
	int cp1 = Read(), cp2 = Read();
	double max1 = 0, max2 = 0;
	for (int i = 0; i<popu; i++)
	{
		max1 = max(max1, friends[cp1][i]);
		max2 = max(max2, friends[cp2][i]);
	}
 
	if (max1 == friends[cp1][cp2] && max2 == friends[cp1][cp2])
	{
		Print(cp1, cp2);
	}
	else
	{
		for (int i = 0; i<popu; i++)
		{
			if (friends[i][cp1] == max1)Print(cp1, i);
		}
		for (int i = 0; i<popu; i++)
		{
			if (friends[i][cp2] == max2)Print(cp2, i);
		}
	}
	return 0;
}

②、通过观察能够发现我的代码思路与上述博主的代码思路基本一致，但又有所不同——判断double值之间是否相等。

//本人判断
fabs(max1-gx[a][pa])<1e-17 && fabs(max2-gx[pa][a])<1e-17
//上述博主判断
max1 == friends[cp1][cp2] && max2 == friends[cp1][cp2]

这里就很奇怪，按照常理来说，double值属于浮点值，而浮点数在计算机中并不能精确的表示是不能直接进行比较的，那么为什么这里又行了？

③、我猜想是不是测试平台的数据有问题，例如只取前几位，于是我修改上述博主的判断。

//上述博主判断源码
max1 == friends[cp1][cp2] && max2 == friends[cp1][cp2]
//修改后
max1 == max2

结果是不能AC，那么这又是什么问题呢？
问了问大佬，貌似其中涉及计算机组成原理的知识，很明显如今弱鸡的我解决不了，等我学了计算机组成原理再来补充吧
欢迎留言讨论 : )

总结

虽然这里没能解决浮点问题，但很好地引起我们对计算机原理的思考，而不单单局限于做题本身，你说对吧？