Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

P5835 [USACO19DEC]Meetings S

Posted on Edited on

可以说是一道比较牛逼的二分+结论的题吧。

感觉自己初赛考完了就没动力了啊，一身疲惫（大雾）。

Solution

首先可以发现时间是具有单调性的，于是可以考虑二分。

对于问题本身，我们可以发现一个很有意思的现象，牛的顺序是不会交换的，这意味着如果两边的牛不到终点的话中间的牛是不可能终点的，现在考虑牛行动的本质，可以发现，如果牛相遇之后他们的方向不会改变，那么这个时间就会很好求，将问题转化成不转向的情况只需在相遇时再交换牛的体重即可。

此时将牛的位置按照$x$排序之后，原来的牛会从哪个方向走出去就加上那边最边上的牛的重量，具体的：

1
2
3
4
int l = 1, r = n, res = 0;
    for(int i = 1;i <= n;i ++)
        if(a[i].d * x + a[i].x <= 0) res += a[l ++].w;
        else if(a[i].d * x + a[i].x >= L) res += a[r --].w;

然后就需要得到相遇的对数，我们再按行动到最后牛的编号排序，每一头牛开始的下标-最后的下标的绝对值就是它会遇到的牛的对数，全部加起来除2即可。

注意，对于已经到$0$和$L$的牛的编号要特殊处理，要按原来的下标排序。

Code

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
#include <bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0;
    bool flag = 0;
    char c = getchar();
    while (c < '0' || '9' < c) { if (c == '-') flag = 1; c = getchar(); }
    while ('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if (flag) res = -res;
}
template <class T, class... ARC>
inline void read(T &res, ARC &...com) { read(res), read(com...); }
template <class T>
void write(T res)
{
    if (res < 0) putchar('-'), res = -res;
    if (res > 9) write(res / 10);
    putchar(res % 10 + '0');
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(const char *s) { while (*s) putchar(*s++); }
template <class T, class... ARC>
inline void write(T res, ARC... com) { write(res), write(com...); }
const int N = 5e4 + 5;
int n, L;
struct Node{
    int w, x, d;
    bool operator< (Node b) const{
        return x < b.x;
    }
}a[N];
int sum;
inline bool check(int x)
{
    int l = 1, r = n, res = 0;
    for(int i = 1;i <= n;i ++)
        if(a[i].d * x + a[i].x <= 0) res += a[l ++].w;
        else if(a[i].d * x + a[i].x >= L) res += a[r --].w;
    return res * 2 >= sum;
}
struct point{
    int id, x;
    bool operator< (point b) const{
        if(x == b.x) return (x == 0 || x == L) ? id < b.id : id > b.id;
        return x < b.x;
    }
}b[N];
int ans;
int main()
{
    // freopen("1.in", "r", stdin);
    // freopen("1.out", "w", stdout);
    read(n, L);
    for(int i = 1;i <= n;i ++) read(a[i].w, a[i].x, a[i].d), sum += a[i].w;
    sort(a + 1, a + n + 1);
    int l = 0, r = 2e9, k;
    while(l <= r)
    {
        int mid = l + r >> 1;
        if(check(mid)) r = mid - 1, k = mid;
        else l = mid + 1;
    }
    for(int i = 1;i <= n;i ++) 
    {
        b[i].id = i, b[i].x = a[i].d * k + a[i].x;
        if(b[i].x < 0) b[i].x = 0;
        if(b[i].x > L) b[i].x = L;
    }
    sort(b + 1, b + n + 1);
    for(int i = 1;i <= n;i ++) ans += abs(b[i].id - i);
    write(ans / 2);
    return 0;
}