NOIP2012 Day1 T3(贪心+模拟)

正解好难写 QAQ……

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

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

#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;
}

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