7-2 芬兰木棋 结构体排序

7-2 芬兰木棋
分数 25
作者 DAI, Longao
单位 杭州百腾教育科技有限公司
WX20200212-152528.png

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

如果仅击倒 1 根木棋，则得木棋上的分数。
如果击倒 2 根或以上的木棋，则只得击倒根数的分数。（例如击倒 5 根，则得 5 分。）
哲哲固定站在 (0,0) 点上，四周放着若干个小木棋 (X
i
​
,Y
i
​
)，坐标均为整数。每次哲哲可以朝一个方向扔出大木棋，大木棋会打倒这个方向上离哲哲最近的 k 个小木棋。哲哲游戏水平很高超，所以这个 k 可以自由控制。

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

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

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

接下来 N 行，每行 3 个整数 X
i
​
,Y
i
​
,P
i
​
，分别表示木棋放置在 (X
i
​
,Y
i
​
)，木棋上的分数是 P
i
​
。坐标在 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

不会写：17分

猜测可以通过结构体排序，同一斜率的w=1的点总共算一次，但是遇到了不为1的点后，需要将标记重置
仅用map的话没办法按照顺序判断

#include<bits/stdc++.h> 
 
using namespace std;
int ans,cnt;
map<double,bool> st1,st2;

bool x1,x2;

int main()
{
	int n;cin>>n;
	while(n--)
	{
		//int x,y;
		double x,y;
		int w;cin>>x>>y>>w;
		
		if(w==1)
		{
			double k=y*1.0/x;
			if(x)
			
			if(y>0){
				if(st1[k]==false){
					st1[k]=true;
					cnt++;
				}
			}else if(y==0){
				if(x>0&&x1==false){
					x1=true;
					cnt++;
				}
				if(x<0&&x2==false){
					x2=true;
					cnt++;
				}
			}else {
				if(st2[k]==false){
					st2[k]=true;
					cnt++;
				}
			}
			
		}
		else cnt++;
		ans+=w;
	} 
	cout<<ans<<" "<<cnt;
	return 0;
}
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
44
45
46
47
48
49
50

#include<bits/stdc++.h> 
 
using namespace std;

int ans,cnt;
map<double,bool> st1,st2;
int idx;
struct node
{
	int x,y;
	double k;
	int t=0;
}ns[100005];
int gcd(int a,int b)
{
	return b==0?a:gcd(b,a%b);
}

bool cmp(node a,node b)
{
	if(a.t!=b.t)return a.t<b.t;
	return a.k<b.k;
}
bool x1,x2;

int main()
{
	
	int n;cin>>n;
	while(n--)
	{
		int x,y;
		//double x,y;
		int w;cin>>x>>y>>w;
		
		if(w==1)
		{
			double k=y*1.0/x;
			
			int d=gcd(x,y);
			x/=d;
			y/=d;
			if(y>0)
			{
				ns[idx].x=x;
				ns[idx].y=y;
				ns[idx].k=k;
				ns[idx++].t=1;
			}else if(y<0)
			{
				ns[idx].x=x;
				ns[idx].y=y;
				ns[idx++].k=k;
			}else if(y==0)
			{
				if(x>0&&x1==false)
				{
					cnt++;
					x1=true;
				}
				else if(x<0&&x2==false)
				{
					cnt++;
					x2=true;
				}
			}
			
		}
		else cnt++;
		ans+=w;
	} 
	for(int i=0;i<idx;++i)
	{
		if(i==0){
            cnt++;
            continue;
        }
		if(ns[i-1].t==ns[i].t&&(ns[i-1].x!=ns[i].x||ns[i-1].y!=ns[i].y))
		{
			cnt++;
		}else if(ns[i-1].t!=ns[i].t){
			cnt++;
		}
	}
	cout<<ans<<" "<<cnt;
	return 0;
}
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87