2021 Robocom 省赛 第二题_如果击倒 2 根或以上的木棋,则只得击倒根数的分数。(例如击倒 5 根,则得 5 分。)

原题链接：

PTA | 程序设计类实验辅助教学平台

题面：

芬兰木棋（Mölkky，又称芬兰木柱）是源自芬兰的一项运动。哲哲将这个运动改造成了赛博朋克单人版，现在场上一开始有 N 根立起的小木棋（上面分别标有一个非负整数），哲哲投掷一根大木棋去击倒这些小木棋以获得分数。分数规则如下：

• 如果仅击倒 1 根木棋，则得木棋上的分数。
• 如果击倒 2 根或以上的木棋，则只得击倒根数的分数。（例如击倒 5 根，则得 5 分。）

哲哲固定站在 (0,0) 点上，四周放着若干个小木棋 (Xi​,Yi​)，坐标均为整数。每次哲哲可以朝一个方向扔出大木棋，大木棋会打倒这个方向上离哲哲最近的 k 个小木棋。哲哲游戏水平很高超，所以这个 k 可以自由控制。

请问哲哲最多能拿多少分，在获得最多分数的情况下最少需要扔出多少次大木棋？

规则与真实规则有较大出入，真实游玩时请以国际莫尔基组织的规则为准

输入格式:

输入第一行是一个正整数 N (1 ≤ N ≤ 105)，表示场上一开始有 N 个木棋。

接下来 N 行，每行 3 个整数 Xi​,Yi​,Pi​，分别表示木棋放置在 (Xi​,Yi​)，木棋上的分数是 Pi​。坐标在 32 位整数范围内，分数为小于等于 1000 的正整数。

保证 (0,0) 点没有木棋，也没有木棋重叠放置。

输出格式:

输出一行两个数，表示最多分数以及获得最多分数最少需要投掷大木棋多少次。

输入样例:

11
1 2 2
2 4 3
3 6 4
-1 2 2
-2 4 3
-3 6 4
-1 -2 1
-2 -4 1
-3 -6 1
-4 -8 2
2 -1 999

输出样例:

1022 9

解题思路：

将所有的棋子坐标按照斜率分类，然后再分别进行排序处理。

代码（CPP）：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int n;
struct Point
{
    int x, y, point;
} chess[maxn];
map<double, vector<Point>> mp;  // 将所有的棋子坐标按照斜率分类
 
bool cmp(Point a, Point b)
{
    if(a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    int sum = 0, cnt = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> chess[i].x >> chess[i].y >> chess[i].point;
        sum += chess[i].point;
        mp[chess[i].y * 1.0 / chess[i].x * 1.0].push_back(chess[i]);
    }
    for(auto p : mp)
    {
        
        vector<Point> temp = p.second;
        sort(temp.begin(), temp.end(), cmp);
        for (int i = 0; i < temp.size(); i++)
        {
            if(i == 0 || temp[i].point != 1 || temp[i - 1].point != 1)
                cnt++;
        }
    }
    cout << sum << " " << cnt;
    return 0;
}