NOIP2012 Day1 T3(贪心+模拟)

正解好难写 QAQ……

这里讲讲 70 分做法。
我们观察发现一个点出边只有最小和次小有用。所以 $O(n^2)$ 预处理最小和次小边,然后之后模拟即可。
预处理可以用大分类讨论,也可以先找最小边,然后标记最小边以后再找当前最小边作为次小边。
分类讨论好想容易错,要讨论很多情况,而且还有高度不同远近的定义,就更困难了,代码中有两种方法,可以看一看。

知识点:
1、浮点数如果能得出分子分母可以直接 gcd 约分后比较整数。
2、分类讨论可以改成枚举或者可以想想其他方法能否更方便替换。

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const LL ZINF = 4223372036854775807ll;
const db eps = 1e-10;
int n;
LL h[1005], X0;
LL l_val[1005], cl_val[1005];//min val, cimin val
int l_no[1005], cl_no[1005];//min no, cimin no
LL abss(LL x) {return x > 0 ? x : -x;}
LL gcd(LL a, LL b) {return b == 0 ? a : gcd(b, a % b);}
void clean() {
for (int i = 0; i <= n; ++i) l_val[i] = cl_val[i] = ZINF, l_no[i] = cl_no[i] = 0;
}
int solve() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%lld", &h[i]);
scanf("%lld", &X0);
clean();
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) if (i != j) {
LL d = abss(h[i] - h[j]);
if (l_val[i] > d) {// d -> min
cl_val[i] = l_val[i], cl_no[i] = l_no[i];
l_val[i] = d, l_no[i] = j;//1
} else {
if (l_val[i] == d) {// d -> min
if (h[l_no[i]] > h[j]) {
cl_val[i] = l_val[i], cl_no[i] = l_no[i];
l_val[i] = d, l_no[i] = j;//1
} else {// d -> cimin
if (cl_val[i] > d) cl_val[i] = d, cl_no[i] = j;//2
else if (h[cl_no[i]] > h[j]) cl_val[i] = d, cl_no[i] = j;//2
}
} else {//d -> cimin
if (cl_val[i] > d) cl_val[i] = d, cl_no[i] = j;//2
else if (cl_val[i] == d && h[cl_no[i]] > h[j]) cl_val[i] = d, cl_no[i] = j;//2
}
}
}
}
/*for (int i = 1; i <= n; ++i) {
int pos = 0;
for (int j = i + 1; j <= n; ++j) if (i != j) {
LL d = abss(h[i] - h[j]);
if (l_val[i] > d) {
l_val[i] = d, l_no[i] = j, pos = j;
} else if (l_val[i] == d) {
if (h[l_no[i]] > h[j]) l_val[i] = d, l_no[i] = j, pos = j;
}
}
for (int j = i + 1; j <= n; ++j) if (i != j && j != pos) {
LL d = abss(h[i] - h[j]);
if (cl_val[i] > d) {
cl_val[i] = d, cl_no[i] = j;
} else if (cl_val[i] == d) {
if (h[cl_no[i]] > h[j]) cl_val[i] = d, cl_no[i] = j;
}
}
}*/
// for (int i = 1; i <= n; ++i) printf("%d ", l_no[i]);
// for (int i = 1; i <= n; ++i) printf("%d ", cl_no[i]);
db whw = ZINF; int ans1 = 0;
LL ansA = 0, ansB = 0;
for (int st = 1; st <= n; ++st) {
LL Sa = 0, Sb = 0;
int cur = 0, now = st;
while (1) {
if (cur == 0) {
Sa += cl_val[now];
if (Sa + Sb > X0) {Sa -= cl_val[now]; break;}
now = cl_no[now];
} else {
Sb += l_val[now];
if (Sa + Sb > X0) {Sb -= l_val[now]; break;}
now = l_no[now];
}
cur ^= 1;
if (now == 0) break;
}
if (Sb == 0) continue ; else {
db tmp = (db)Sa / (db)Sb;
if (whw - tmp > eps) whw = tmp, ans1 = st, ansA = Sa, ansB = Sb;
LL g = gcd(Sa, Sb); Sa /= g, Sb /= g;
if (Sa == ansA && Sb == ansB && h[st] > h[ans1]) ans1 = st;
}
}
printf("%d\n", ans1);
int Q; scanf("%d", &Q);
while (Q--) {
int st;
LL X; scanf("%d%lld", &st, &X);
LL Sa = 0, Sb = 0;
int cur = 0, now = st;
while (1) {
if (cur == 0) {
Sa += cl_val[now];
if (Sa + Sb > X) {Sa -= cl_val[now]; break;}
now = cl_no[now];
} else {
Sb += l_val[now];
if (Sa + Sb > X) {Sb -= l_val[now]; break;}
now = l_no[now];
}
cur ^= 1;
if (now == 0) break;
}
printf("%lld %lld\n", Sa, Sb);
}
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}

------ 本文结束 ------