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

痛定思痛。 2022-12-22 06:19 174阅读 0赞

#### 前言 ####

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

### [秀恩爱分得快][Link 1] ###

![题目1][1]  
![题目2][2]

--------------------

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

### 实现 ###

下面是我借鉴 [其他博主][Link 2] 改善的代码

#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 类型就会出现超时？？？

--------------------

### 讨论 ###

讨论形式是对其他博主的代码进行思考->[其他博主][Link 2]  
（该博主的代码也能够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，那么这又是什么问题呢？  
问了问大佬，貌似其中涉及计算机组成原理的知识，很明显如今弱鸡的我解决不了，等我学了计算机组成原理再来补充吧  
欢迎留言讨论 : )

### 总结 ###

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

[Link 1]: https://pintia.cn/problem-sets/994805046380707840/problems/994805054698012672
[1]: /images/20221120/931fbc59e3d2498e8683615d34895294.png
[2]: /images/20221120/7df809cc7b714035ae5d6c99d2d4b0e2.png
[Link 2]: https://blog.csdn.net/qq_43700916/article/details/88827106?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160566791719725222432615%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=160566791719725222432615&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_v2~rank_v28_p-13-88827106.pc_first_rank_v2_rank_v28p&utm_term=%E7%A7%80%E6%81%A9%E7%88%B1%E5%88%86%E5%BE%97%E5%BF%AB&spm=1018.2118.3001.4449