题解 P5835 【[USACO19DEC]Meetings会议】

· · 题解

出题神仙 Benq 已经说了，这题放在银组还是比较难的。

(Analysis by Benjamin Qi)
Note: This problem is quite tricky for silver!

考场上懵了，去学校之后问了 EternalAlexander 神仙，他做的，代码是我的。

思路：（时间复杂度 O(N \log^2 N)） 有两个重要的结论：

  1. 最后各头牛的坐标值，在不考虑顺序的情况下，等于没有对冲的坐标值。因为两头牛做的是对撞。

  2. 最后各头牛的相对顺序不变。还是因为反弹。

开始先按初始坐标从小到大排个序。

显然这题分为两步：求 T；求相遇次数。

  1. 求 T 可以二分答案。
    check 函数中，根据结论 1 算出末坐标，然后记录原编号按末坐标排序，这时初坐标和末坐标就对应了。简单计算是否满足条件即可。

  2. 记录原编号就是用来做第二步的。
    记录末坐标的数组按初坐标和末坐标大小两种方式排序，会得到两种相对顺序。这两种相对顺序应该是两个 1 \dots N 的排列。树状数组求逆序对即可。

这算法很明显是对的，但我的代码通不过第二个点，比标答小 1。评论有无大佬告诉我为什么？

#include <bits/stdc++.h>

#define ll long long
#define rgi register int

#define sp putchar(32)
#define el putchar(10)

#define pb push_back
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second

#define filein(x) freopen(x, "r", stdin)
#define fileout(x) freopen(x, "w", stdout)

using namespace std;

const int maxn = 5e4 + 5;
int n, L, ans, sum;
struct cow {
    int w, x, d;
}a[maxn];
struct tmp {
    int id, y;
}b[maxn];
int c[maxn];

inline bool cmp1(cow p, cow q) { return p.x < q.x; }
inline bool cmp2(tmp p, tmp q) {
    if (p.y != q.y) return p.y < q.y;
    else return p.id < q.id;
}

bool check(int tim) {
    for (rgi i = 1; i <= n; ++i) {
        b[i].id = i;
        b[i].y = a[i].x + a[i].d * tim;
    }
    sort(b + 1, b + n + 1, cmp2);
    int tans = 0;
    for (rgi i = 1; i <= n; ++i)
        if (b[i].y < 0 || b[i].y > L)
            tans += a[i].w;
    if ((tans << 1) >= sum) return 1;
    else return 0;
}

inline int lowbit(int x) { return x & (-x); }
inline void add(int i, int x) {
    for (; i <= n; i += lowbit(i)) c[i] += x;
}
inline int query(int i) {
    int ret = 0;
    for (; i; i -= lowbit(i)) ret += c[i];
    return ret;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    filein("meetings.in"), fileout("meetings.out");
    cin >> n >> L;
    for (rgi i = 1; i <= n; ++i) {
        b[i].id = i;
        cin >> a[i].w >> a[i].x >> a[i].d;
        sum += a[i].w;
    }
    sort(a + 1, a + n + 1, cmp1);

    int l = 0, r = L;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    for (rgi i = 1; i <= n; ++i) {
        add(b[i].id, 1);
        ans += i - query(b[i].id);
    }
    cout << ans << endl;
    return 0;
}