题解：P10190 [USACO24FEB] Target Practice II S

· · 题解

P10190 [USACO24FEB] Target Practice II S

题墓链接

做法：二分答案。
与一般的二分答案有些区别，一般的二分是二分结果的，是距离，但这个题没有具体的端点，于是我们考虑二分两个端点。

题意简述：

说实话本题我理解了挺久的，发现画个图会更好理解。

平面直角坐标系中，共有 n 个矩形(依次出现)，我们认为每个矩形的四个顶点为奶牛需要射击的靶子，题目给出 4n 头在 y 轴上的奶牛的射击斜率，我们要给每个奶牛分配一个一一对应的靶子，然后奶牛就会在 y 轴上有一个对应的位置。
要求：射击的过程中不穿过矩形内部(因为矩形依次出现，所以我们只需考虑单个矩形即可)。
最终要使最高的奶牛和最低的奶牛的距离差值最小。

注意题目中的细节：每个矩形的左边那条边所在的 x (即 X1 )不变。
下面给出样例(第一个)。

2 1
1 3 6
4 6 3
1 -1 2 -2 3 -3 4 -4


可以看到两个矩形的左边的边都在 x = 1 轴上。

现在我们考虑怎么把奶牛放在 y 轴上。
经过简单分析题目的要求，我们可以发现对于每个矩形右上的顶点，我们只能用一个射击斜率为负数的奶牛来打。
同理，对于右下角，我们只能用斜率正数的奶牛来打。

因此，当我们把正数或负数的奶牛用完之后，如果矩形右端的对应顶点没有被打完，这就是题目中的无解情况，输出 -1。

无解的情况处理完了，那怎么使最高的奶牛和最低奶牛这个距离差最小呢？

首先，我们是可以贪心确定每个顶点对应的是正斜率的奶牛还是负斜率的奶牛的。
右顶点就不赘述了。对于左顶点，因为正斜率的奶牛射击时肯定是在要射击顶点的下方，而负斜率的奶牛相反，在上方。又因为左顶点都在同一根轴上，为了满足距离差最小，我们会将正斜率的奶牛尽量分给靠上的顶点，而负斜率就是靠下的顶点。
先用两个 vector 数组分别存哪些顶点给正斜率，哪些给负斜率，方便后面的检查。

一般看到最值，不难想到二分的做法。但是这个题没法直接二分这个距离，因此我们要二分最高奶牛和最低奶牛的位置，然后再判断有没有一种方案，可以让左右奶牛都在这个范围内，是满足单调性的。

至于怎么判断，我用一个图解释。

假设我们当前二分到这个绿色的 min 点，我们要保证所有奶牛的位置大于等于它。拿所有奶牛的斜率算位置有点麻烦？那我们就考虑拿斜率比较呗 qwq。

我们把点 min 与所有矩形上的顶点连一条边(图上仅连了一条)，我们可以计算这些边的斜率。显然，一个奶牛的位置在 min 之上，当且仅当这个奶牛的斜率小于等于我们所计算的斜率。

我们需要一个东西，它可以快速找到一堆数中大于等于一个数的最小的数，并且把它删除(每只奶牛仅用一次)。

是的没错就是集合。
我们把正斜率的奶牛和负斜率的奶牛分别存到两个集合里面方便判断。由于不知道有没有斜率重复的奶牛，我们用多重集合。

以上是求 min 的过程，求 max 同理，有一些细节上的不同，所以要写两个二分。

因为两个二分有大部分重复内容，代码有点长。
复杂度 O(n \log n)。

#include <bits/stdc++.h>
#define rep(i,a,n) for(int (i)=(a);(i)<=(n);(i)++)
#define pre(i,a,n) for(int (i)=(a);(i)>=(n);(i)--)
#define ull unsigned long long
#define int long long
#define y11 y1
#define pb push_back
using namespace std;
const int N = 40000 + 10;
struct node
{
    int x, y;
    bool operator < (const node &nd) const { 
        return y < nd.y;
    }
};
int n, x1;
int s[N];
multiset<int> st1, st2; //分别存斜率大于0和斜率小于零的牛 
vector<node> va, vb, vc; //分别存最终用斜率大于0的牛射击的点和用斜率小于0射击的点 
bool check1(int mid)
{
    multiset<int> st = st1;
    for (node &t : va)
    {
        int s = (t.y - mid) / t.x;
        auto k = st.upper_bound(s);
        if (k == st.begin()) return false; 
        k--; //取 >s 的前一个数 
        st.erase(k);
    }
    return true;
}
bool check2(int mid)
{
    multiset<int> st = st2;
    for (node &t : vb)
    {
        int s = (t.y - mid) / t.x;
        auto k = st.lower_bound(s); //取大于等于s的第一个数 
        if (k == st.end()) return false; 
        st.erase(k);
    }
    return true;
}
void init()
{
    va.clear(), vb.clear(), vc.clear();
    st1.clear(), st2.clear(); 
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        init(); //多测清空 
        cin >> n >> x1;
        rep(i, 1, n)
        {
            int y1, y2, x2;
            cin >> y1 >> y2 >> x2;
            va.pb(node{x2, y1}); //右下角 
            vb.pb(node{x2, y2}); //右上角
            vc.pb(node{x1, y1}); //轴上的点暂时不确定，先存起来
            vc.pb(node{x1, y2});
        }
        rep(i, 1, 4 * n) 
        {
            int s; cin >> s;
            if (s > 0) st1.insert(s); //正斜率集合
            else st2.insert(s); //负斜率集合
        }
        if (st1.size() < n || st2.size() < n) //右侧的端点无法安排牛 
        {
            cout << -1 << "\n";
            continue; 
        }
        sort(vc.begin(), vc.end()); //将轴上的点按高低排序 
        int cnt = n;
        for (node t : vc)
        {
            if (cnt < st1.size()) va.pb(t), cnt++; //分配轴上的点
            else vb.pb(t);
        }
        int r = vc[0].y, l = -1e18, mid, mi, mx = 0;
        while (l <= r) //二分最大的最小端点
        {
            mid = l + r >> 1;
            if (check1(mid))
            {
                mi = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        l = vc.back().y, r = 1e18;
        while (l <= r) //二分最小的最大端点
        {
            mid = l + r >> 1;
            if (check2(mid))
            {
                mx = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        cout << mx - mi << "\n";
    }
    return 0;
}

完结撒花\OWO/。