P10192 题解

Guizy · 2024-03-16 14:03:43 · 题解

我们可以开一个 even 数组和一个 odd 数组，分别记录到了第 i 轮时选偶数和奇数的最坏情况要赚多少（亏了就是负数）。

for(int i=1;i<=m;i++){
    maxe=maxo=-1,mine=mino=INT_MAX;
    for(int j=1;j<=k;j++){
        scanf("%lld",&a[i][j]);
        if(!(a[i][j]&1)) maxe=max(maxe,a[i][j]),mine=min(mine,a[i][j]);
        else maxo=max(maxo,a[i][j]),mino=min(mino,a[i][j]);
    }
    if(maxe==-1) even[i]=-maxo,odd[i]=mino;
    else if(maxo==-1) even[i]=mine,odd[i]=-maxe;
    else even[i]=-maxo,odd[i]=-maxe;
}

有了这两个数组，我们就可以求一段区间内的最优解。

既然要字典序最小，那我们就要从前往后枚举，能选 Even 就选 Even，否则选 Odd。

如何判断能否选 Even？

如果当前的石子数量加上 even_i 再加上 [i,n] 的最优解大于 0，并且当前石子数量加上 even_i 大于 0 就可以（因为石子数量不能是负数）。否则不行。

这时我们就要用一个后缀和数组 suf 记录，suf_i 表示 [i,n] 的最优解。

判断能否选 Odd 同理。

如果两个都不能选，那么输出 -1 跑路。

Tips：计算 suf 的时候要对 0 取 \min，否则程序在判断能否选 Even 的时候以为后面可以赚回来，石子数就可能会形成一个正数到负数再回到正数的过程，然后到了后面程序发现石子数为负了，就会输出 -1。感觉说的有点抽象，不懂的可以去看 #3 的倒数第二组手模一下。

for(int i=m;i>=1;i--)
    suf[i]=min(0ll,suf[i+1]+max(even[i],odd[i]));//Tips
for(int i=1;i<=m;i++){
    if(n+even[i]+suf[i+1]>0&&n+even[i]>0)
        ans+="Even ",n+=even[i];
    else if(n+odd[i]+suf[i+1]>0&&n+odd[i]>0)
        ans+="Odd ",n+=odd[i];
    else{
        puts("-1"),flag=0;
        break;
    }
}