USACO-[USACO23FEB] Bakery S 题解

· · 题解

USACO Feb S组 T1

题意简述：

假设三元组(A, B, C),每次用1的代价将A*tc+B*tm\leq C 中的tc, tm其中之一减1，最终使得所有的三元组符合上述不等式，求得最小的代价。(1\leq A,B,tc,tm\leq 1e9,1\leq C\leq 1e18)

题目分析：

将初始二元组\{tC, tM\}向左下移动使得所有的不等式成立的最小代价，假设最终为(tc', tm'),则最小代价为(tC - tc') + (tM - tm')。

我们将tc设为x, tm设为y则这个不等式为Ax + By \leq C \rightarrow y \leq -\frac{A}{B}x+\frac{C}{B}(B \geq1)。

上述不等式就可以化为一个一次函数的区域在坐标轴上。

算出每两条线段的交点。

先考虑实数范围，首先题意答案一定在红色区域内。

再证明一定再上凸壳上：因为加入说再红色区域内但又不在上凸壳上则可以向上平移使得答案更优。

在证明一定在交点上：因为：

再每一个代入(x, y)求解算得最小代价。

细节1： 有边界1. y = tM, 2. x = tC, 交点不能超过这两个3. x = 1, 4. y = 1 直线还要与这两个取交点。

细节2： 求得每一个交点不一定都是整数,所以要取整。怎么取整：应当先向下取整之后再将横坐标或纵坐标试着加1，看看是否满足在凸包内。

代码：

#include <bits/stdc++.h>

#define rep(i, a, b) for(int i = (a); i <= (b); i ++)
#define per(i, a, b) for(int i = (a); i >= (b); i --)
typedef __int128 big;

#define LL long long
#define ULL unsigned long long
#define PII pair<int, int>
#define PIL pair<int, long long>
#define PLI pair<long long, int>
#define PLL pair<long long, long long>
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define sf scanf
#define prf printf
#define el putchar('\n')
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define mmc(arr1, arr2) memcpy(arr1, arr2, sizeof(arr2))
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int mod = ;

template <typename T> inline void rd(T &x){
    x = 0; bool f = true; char ch = getchar();
    while(ch < '0' || ch > '9'){ f = ((ch == '-') ? false : true); ch = getchar();}
    while(ch >= '0' && ch <= '9'){ x = (x << 1) + (x << 3) + (ch ^ '0'); ch = getchar();}
    if(!f) x = -x;
}
template <typename T, typename ...Args> inline void rd(T &x, Args &...args){ rd(x); rd(args...);}

using namespace std;

const int N = 110;
int n; LL a[N], b[N], sx, sy, c[N];
int t; LL x[10 * N * N], y[10 * N * N];

void clear() {t = 0;}

void solve() {
    rd(n, sx, sy); clear();
    rep(i, 1, n) rd(a[i], b[i], c[i]);

    auto add = [](LL x_, LL y_) {
        rep(dx, -1, 1) rep(dy, -1, 1) {
            LL cx = x_ + dx;
            LL cy = y_ + dy;
            if(cx >= 1 && cx <= sx && cy >= 1 && cy <= sy) t ++, x[t] = cx, y[t] = cy;
        }
    };

    add(1, 1), add(sx, 1), add(1, sy), add(sx, sy);

    rep(i, 1, n) rep(j, i + 1, n) {
        if(a[i] * b[j] == a[j] * b[i]) continue;
        big cx_ = ((big)c[i] * b[j] - (big)c[j] * b[i]) / (a[i] * b[j] - a[j] * b[i]);
        if(cx_ > sx || cx_ < 1) continue; 
        LL cx = cx_;
        LL cy = min((c[i] - cx * a[i]) / b[i], (c[j] - cx * a[j]) / b[j]);
        add(cx, cy);
    }
    rep(i, 1, n) {
        LL cy = (c[i] - sx * a[i]) / b[i]; if(cy <= sy && cy >= 1) add(sx, cy);
        LL cx = (c[i] - sy * b[i]) / a[i]; if(cx <= sx && cx >= 1) add(cx, sy);

        cy = (c[i] - a[i]) / b[i]; if(cy <= sy && cy >= 1) add(1, cy);
        cx = (c[i] - b[i]) / a[i]; if(cx <= sx && cx >= 1) add(cx, 1);
    }

    LL ans = 0;

    rep(i, 1, t) {
        bool flag = true;
        rep(j, 1, n) if(b[j] * y[i] > c[j] - a[j] * x[i]) {flag = false; break;}
        if(flag) ans = max(ans, x[i] + y[i]);
    }

    printf("%lld\n", sx + sy - ans);
}

int main(){

    int tt; rd(tt); while(tt --) solve(); return 0;
}