问什么不能贪心?(30pts)
查看原帖
问什么不能贪心?(30pts)
431956
_k_e_v_i_n_楼主2022/10/30 12:02
#include <bits/stdc++.h>
using namespace std;
int n, m, a[1005], x[1005], y[1005], ans;
double minn, maxx;
double calc(int x1, int y1, int x2, int y2){
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
int main(){
	cin >> n;
	for (int i = 1; i <= n; i++)	cin >> a[i];
	cin >> m;
	for (int i = 1; i <= m; i++){
		cin >> x[i] >> y[i];
	}
	for (int i = 1; i <= m; i++){
		minn = 1e9;
		for (int j = 1; j <= m; j++){
			if (i != j){
				minn = min(minn, calc(x[i], y[i], x[j], y[j]));
			}
		}
		maxx = max(minn, maxx);
	}
	for (int i = 1; i <= n; i++){
		if (a[i] >= maxx){
			ans++;
		}
	}
	cout << ans;
	return 0;
}

思路:枚举每棵树,找到与它最近的树,然后在所有树中取最大的,看哪些猴子能跳过去。

问:问什么不行?

2022/10/30 12:02
加载中...