题解 P8092 [USACO22JAN] Drought B

fz20181223 · 2022-02-05 17:57:34 · 题解

这题可以证明答案的单调性。

很明显，令我们当前使每个奶牛的饥饿值降至 x（保证降至 x 是可行的），易证：我们可以将每个奶牛的饥饿值降至 [1,x] 之间的任意数，只需对于每个投喂操作加上对应数量的玉米袋即可（例如我当前设定将所有奶牛饥饿值设为 6，每头奶牛分别需要投喂 a_1,a_2,a_3,\cdots,a_N，如果我将所有奶牛饥饿值改为 4，则只需将每头奶牛投喂的数量改为a_1+2,a_2+2,a_3+2,\cdots,a_N+2）。

故该题可以通过二分最大饥饿值求解。

由于二分左边界为 0，我们为了区分边界是因为二分结果是 0 还是无解，我们可以将初始时左边界设为 -1 以与找到答案区分。检查时我们可以从第一头奶牛开始模拟，看看它能不能降至当前设定的饥饿值，并且逐次向后推，若遇到当前奶牛的饥饿值因为为了满足上一只奶牛而饥饿值降为负数，则说明当前预设是不行的。

值得注意的是我们可能需要一些特判，比如：当奶牛数大于 1 时，第一头奶牛的饥饿值不得大于第二头的饥饿值，且倒数第一头奶牛的饥饿值不得大于倒数第二头的饥饿值。同时，在不满足上述条件且奶牛数不足 3，则答案必为 0（因为不需做任何修改，所有奶牛饥饿值必然一样）。

赛时源代码（有删改）：

#include<bits/stdc++.h>
#define mset(a,x) memset(a,x,sizeof(a))
using namespace std;
const int N=1e5+9;
int n,a[N],b[N];
bool check(int x){
    memcpy(b,a,sizeof(a));
    for(int i=1;i<n;++i){
        if(b[i]<x) return 0;
        b[i+1]-=(b[i]-x);
    }
    return b[n]>=x;
}
void solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",a+i);
    if(n>1&&(a[1]>a[2]||a[n-1]<a[n])){
        puts("-1");
        return;
    }
    if(n<3){
        puts("0");
        return;
    }
    int l=-1,r=1e9+7;
    for(int i=1;i<=n;++i) r=min(r,a[i]);
    int tmp=r;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    if(l>tmp||l<0){
        puts("-1");
        return;
    }
    ll ans=0;
    for(int i=1;i<=n;++i) ans+=(a[i]-l);
    printf("%lld\n",ans);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--)solve();
    return 0;}