题解 CF1764E 【Doremy's Number Line】

VinstaG173 · 2022-11-29 11:35:57 · 题解

~~fk u corner case.~~

贪心+分类讨论。鸣谢 Spasmodic 的 hack 数据帮我找到原贪心的错误点。

对于一个数 x，如果我们想要将它染色 i，则考虑以下情况：

注意到染色方法中所有限制条件都是不超过某个数即可染色，则对于“期望染成任意颜色”的点，若 x 能染色，则不大于 x 的所有点均能染色。因此 4 可改写为：

接下来考虑 k 能否染色 1 由哪些因素决定。若对 x=k,i=1 符合情况 1 或 2，则可以直接判定。若符合情况 3，则可以由除 1 外是否有其他颜色直接判定。事实上即当且仅当 n>1 时可以染色。

对于情况 4，此时只要将 k-b_1 染成除 1 外的任意颜色。我们看作是“花费一种颜色 i，将想要的 k 减去 b_i”的一种操作。这种操作只有在 b_i<k\le a_i+b_i 时才能进行。我们将每次遇到情况 4 时进行这个操作的 i 记录下来，直到遇见情况 1,2,3 为止。考虑这个操作序列的性质。

注意到 b_i\ge1，且随着 k 的减小能操作的颜色数不减，因此对于能够操作的 i，花费颜色 i 减小 k 一定不劣于不减小 k。因此我们认为有贪心策略：一旦存在颜色 i 能够操作，就一定操作之。

发现某时刻能够操作的颜色在 k 减小后依然能够操作，且将操作过的若干颜色 i_1,i_2,\dots,i_m 操作顺序重排（在操作依然合法的情况下）后 k 的最终值 k-\sum\limits_{j=1}^mb_{i_j} 不变，因此我们可以进行合理的重排。不妨将操作序列以 a_i+b_i 从大到小的顺序排序。显然这样排序后所有操作必定合法。

接下来我们认为对于 i_1,i_2，若 a_{i_1}+b_{i_1}<a_{i_2}+b_{i_2}，且 i_1 在操作序列中，则 i_2 必在操作序列中。由于操作 i_1 时 k\le a_{i_1}+b_{i_1}<a_{i_2}+b_{i_2}，故只要 k>b_{i_2}，i_2 便可以操作。由于可以操作必操作，且操作序列可以按 a_i+b_i 从大到小排序，因此 i_2 必被操作。若 k\le b_{i_2}，则此时存在 i_1 尚未操作，已经可以结束染色。

因此最终操作序列必然为 a_i+b_i 最大的若干个 i，操作结束后的 k 不再符合情况 4，此时根据情况 1,2,3 即可作出判断。

综上，我们得到贪心策略：

对于颜色 1 判断是否符合情况 1,2,3，若为情况 4 则将 k 变为 k-b_1；
将颜色 2,3,\dots,n 按 a_i+b_i 从大到小排序；
对于排序后的序列，每次取出 a_i+b_i 最大且没有操作过的颜色，判断是否符合情况 1,2,3，若为情况 4 则将 k 变为 k-b_i，重复进行这一步。

但是很遗憾，这样的贪心策略是错误的。以下是 Spasmodic 提供的 hack 数据：

对于这组数据，我们直接以 a_i+b_i 排序后得到的颜色序列是 3,2，当前 k=141-1=140，对于 i=3 符合情况 4。接下来当前 k=140-50=90，对于 i=2 符合情况 3，但是此时已经没有其他颜色可以染了，于是我们判断结果为 NO。

但是我们发现若先操作颜色 2，会将 k 变为 140-90=50，此时对于 i=3 符合情况 1，故结果为 YES。

分析一下我们会发现问题出在最后的结论：对于 i_1,i_2，若 a_{i_1}+b_{i_1}<a_{i_2}+b_{i_2}，且 i_1 在操作序列中，则 i_2 必在操作序列中。进而分析发现策略“可以操作必操作”是存在问题的。

事实上这个结论在几乎所有情况下都是正确的，只有在一种情况下会出错，就是只剩下 i_1,i_2 两种颜色未操作时。

这个错误出现的本质原因是情况 4 对于最后一种未染的颜色的后续不是进行操作，而是直接判定为 NO 并结束。因此若只剩下两种颜色可染，操作其中一种颜色后另一种颜色将不能被操作，“随着 k 的减小能操作的颜色数不减”变为假命题。

这个错误的解决方案也很简单，由于只剩两种颜色，我们将它们的优先顺序调换后再做一次相同的贪心，只要有一次判定为 YES 即成功，否则判定为 NO。

时间复杂度瓶颈在排序的 O(n\log n)。

Code:

int n,k,_k;
int id[100003];
int a[100003],b[100003];
inline int cmp(int x,int y){
    if(a[x]+b[x]==a[y]+b[y])
        return b[x]>=b[y];
    return a[x]+b[x]>a[y]+b[y];
}void solve(){rd(n);rd(k);
    for(rg int i=1;i<=n;++i){
        rd(a[i]);rd(b[i]);id[i]=i;
    }if(k<=a[1]){puts("YES");return;}
    if(k<=b[1]){puts((n>1)?"YES":"NO");return;}
    if(k>a[1]+b[1]){puts("NO");return;}
    k-=b[1];_k=k;sort(id+2,id+n+1,cmp);
    for(rg int _i=2,i;_i<=n;++_i){
        i=id[_i];if(a[i]+b[i]<k)break;
        if(k<=a[i]){puts("YES");return;}
        if(k<=b[i]&&_i<n){puts("YES");return;}
        k-=b[i];
    }if(n>2){id[n-1]^=id[n]^=id[n-1]^=id[n];k=_k;
        for(rg int _i=2,i;_i<=n;++_i){
            i=id[_i];if(a[i]+b[i]<k)break;
            if(k<=a[i]){puts("YES");return;}
            if(k<=b[i]){puts((_i<n)?"YES":"NO");return;}
            k-=b[i];
    }}puts("NO");
}