7-2 芬兰木棋
问题描述
我们有一项改编自芬兰木棋的运动，场上有N根标有非负整数的小木棋，哲哲投掷大木棋击倒这些小木棋来得分。得分规则如下：
- 如果仅击倒1根木棋，则得木棋上的分数。
- 如果击倒2根或以上的木棋，则只得击倒根数的分数。
我们需要求解：
- 哲哲最多能拿多少分？
- 在获得最多分数的情况下，最少需要扔出多少次大木棋？
输入格式
- 第一行是一个正整数 N (1 ≤ N ≤ 10^5)，表示场上有N个木棋。
- 接下来N行，每行三个整数 X_i, Y_i, P_i，分别表示木棋的坐标和木棋上的分数。坐标在32位整数范围内，分数为小于等于1000的正整数。
输出格式
- 输出一行两个数，表示最多分数以及获得最多分数最少需要投掷大木棋多少次。
思路解析
要解决这个问题，我们需要从两个方面考虑：
- 最大化得分：在一个方向上尽量击倒得分最高的木棋。
- 最小化投掷次数：在尽量少的投掷次数下击倒最多的木棋。
具体步骤
- 读取输入数据：将所有木棋的信息读入并计算每个木棋到(0,0)的距离。
- 按距离排序：将木棋按与原点距离从近到远排序。
- 按方向统计：使用一个哈希表来记录各个方向上能击倒的木棋数量和得分。
- 遍历木棋：对每个木棋，计算其方向（向量形式），使用GCD简化方向向量，使不同但同方向的向量统一，然后记录该方向上的木棋。
- 计算得分和投掷次数：最后统计所有方向上的得分和所需投掷次数。
代码实现
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 5;
int gcd(int a, int b) {
return __gcd(a, b);
}
struct Node {
int x, y, p, dis;
// 重载小于运算符，按照 dis 进行排序
bool operator<(const Node& other) const {
return dis < other.dis;
}
};
Node node[N];
map<PII, int> mp;
signed main() {
int n;
cin >> n;
int sum = 0;
int ci = 0;
for (int i = 1; i <= n; i++) {
int x, y, p;
cin >> x >> y >> p;
node[i].x = x;
node[i].y = y;
node[i].p = p;
node[i].dis = x * x + y * y; // 计算距离的平方，避免浮点误差
sum += p;
}
// 按距离从近到远排序
sort(node + 1, node + 1 + n);
for (int i = 1; i <= n; i++) {
int p = node[i].p;
int x = node[i].x;
int y = node[i].y;
// 计算方向向量的简化形式
int g = abs(gcd(x, y));
x /= g;
y /= g;
if (p > 1) {
// 如果木棋得分大于1，记录一次投掷
ci++;
mp[{x, y}] = 0; // 重置这个方向的计数
} else {
// 如果木棋得分等于1，且这个方向还没有记录过，则记录一次投掷
if (mp[{x, y}] == 0) {
ci++;
mp[{x, y}]++;
}
}
}
cout << sum << " " << ci << endl;
return 0;
}
详细解释
-
数据结构：
Node结构体记录木棋的坐标、分数和距离平方。map<PII, int>哈希表记录每个方向上的木棋。
-
GCD简化向量方向：
- 对于每个木棋，计算其与原点的方向向量，然后用GCD简化，使同方向的向量统一表示。
-
排序和统计：
- 按照距离排序，从近到远处理木棋，确保优先击倒离原点最近的木棋。
- 对于每个木棋，检查其方向向量，如果得分大于1，记录一次投掷并重置该方向计数。
- 如果得分为1，且该方向还没有投掷过，则记录一次投掷。
结果
代码首先计算出哲哲能够获得的最大得分，然后计算出获得最大得分所需的最少投掷次数。
原文地址：https://blog.csdn.net/weixin_73412387/article/details/140418976
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！