7-2 芬兰木棋

时间限制
400 ms
内存限制
64 MB

题意：

• 如果击倒一根，获得这根上的分数；如果击倒大于等于两根，则击倒的根的分数等于1，累加；
• 每次可以控制同一个方向上，从近到远的 任意数量 的根数
• 无限次，问最大分数，以及最大分数下的最小次数

思路 ：

• 如果击倒大于等于2根，击倒的所有分数都变成了1，因此大于1的最好是一根拿，等于1怎么拿对分数无影响，在最大分数情况下，最好是多根拿；因此，最大分数就是所有和
• 最小次数，按方向枚举，因此用到map；不是连续的1就单独拿
• 循环时，只要进入循环，首先cnt++，然后找下一个可以直接++的位置
• 排序时，由于只需要保证不是连续的1就单独拿，因此其实从近到远和从远到近是等价的，因此，我们将方向作为枚举依据，不需要考虑象限，直接从最左边到最右边
• 注意斜率方向double，且在算斜率时也要 * 1.0
• 注意如果x为0时，算出的斜率是null，map的key值可以是null，这个时候，如果x都为0，则按y排

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

struct Node {
    int x, y, v;
    bool operator< (const Node &w) const {
        return x != w.x ? x < w.x : y < w.y;
    }
};

int n;
map<double, vector<Node>> ma;

int main() {
    cin >> n;
    int sum = 0;
    for (int i = 0; i < n; ++ i) {
        int x, y, v;
        cin >> x >> y >> v;
        sum += v;
        ma[y * 1.0 / x].push_back({x, y, v});
    }
    cout << sum << ' ';
    int cnt = 0;
    for (auto x : ma) {
        vector<Node> ve = x.second;
        sort(ve.begin(), ve.end());
        for (int i = 0; i < (int)ve.size(); ++ i) {
            cnt ++ ;
            if (ve[i].v == 1) {
                int j = i;
                while (j < ve.size() && ve[j].v == ve[i].v) j ++ ;
                j -- ;
                i = j;
            }
        }
    }
    cout << cnt;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43