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;
}
------ 本文结束 ------