Codeforces Round700 div2部分题题解

题解"/>

Codeforces Round700 div2部分题题解

B.The Great Hero

英雄有 A ( 1 ≤ A ≤ 1 0 9 ) A(1\leq A \leq 10^9) A(1≤A≤109)的攻击， B ( 1 ≤ B ≤ 1 0 9 ) B(1\leq B \leq 10^9) B(1≤B≤109)的血量。有 n ( 1 ≤ n ≤ 1 0 5 ) n(1\leq n \leq 10^5) n(1≤n≤105)只怪物，每只怪物有 a i ( 1 ≤ a i ≤ 1 0 9 ) a_i(1\leq a_i \leq 10^9) ai​(1≤ai​≤109)的攻击， b i ( 1 ≤ b i ≤ 1 0 9 ) b_i(1\leq b_i \leq 10^9) bi​(1≤bi​≤109)的血量。英雄可以每次选择一个怪物进行战斗，之后英雄的血量变为 B − a i B-a_i B−ai​，怪物的血量变为 b i − A b_i-A bi​−A。判断对于给定的 n n n只怪物，英雄是否能够战胜（最后同归于尽也算作战胜）。

最初我有一种朴素的想法：假设怪物是3只小兵一个Boss，小兵对英雄没有威胁，但是Boss和英雄可以互秒。那策略显然就是先打小兵，后打Boss。进而想到，对n只怪物排序，能对英雄造成的伤害高的最后打。但这种想法是错的，可以看这组hACk数据：

1
1 100 2
1 11
80 2
// 你的攻击/血量：1 100
// 怪物1的攻击/血量：1 80
// 怪物2的攻击/血量：11 2

仔细想一下，如果这道题没有可以同归于尽这个设定的话，其实这道题就与顺序无关，无论先打哪个都一样。

但由于同归于尽，我们就需要仔细思考了。我们可以这样想：我们将一个需要砍n刀的怪物分成n个攻击力不变，但一刀就可以砍死的怪物(因为战斗是回合制)。这样，每一只怪物与我们战斗都是有同归于尽的可能的。而我们与攻击力高的怪物同归于尽的可能性更大，所以最优策略是攻击力最高的怪物最后打。

进一步地，我们可以找出一个更好写代码的方法：先于所有的怪物战斗（无论怪物的顺序，即便血量降到0以下也继续），然后将血量加上怪物的最高攻击力（这就相当于回到了杀死了所有其他怪物，与最后一只怪物快要同归于尽时的情况）。如果加之后血量仍小于0，说明我们撑不到这个时候，否则我们一定能与最后一只怪物同归于尽。

其实由于数据比较水，枚举每一个怪物作为最后一只与英雄战斗的怪物，并判断战胜其他怪物之后的英雄是否能够战胜它也能卡过去。

AC代码：

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int maxn = 1e5 + 10;
ll a[maxn], b[maxn];int main()
{int t;scanf("%d", &t);while (t--) {ll A, B, n;scanf("%lld%lld%lld", &A, &B, &n);ll maxa = 0;for (int i = 1; i <= n; i++) {scanf("%lld", &a[i]);maxa = max(a[i], maxa);}for (int i = 1; i <= n; i++) {scanf("%lld", &b[i]);}for (int i = 1; i <= n; i++) {if (b[i] % A == 0) {B -= a[i] * (b[i] / A);}else {B -= a[i] * (b[i] / A);B -= a[i];}}B += maxa;if (B > 0) {printf("YES\n");}else {printf("NO\n");}}return 0;
}

C.Searching Local Minimum

D1.Painting the Array I

定义 s e g ( a ) seg(a) seg(a)为合并 a a a中连续相同元素后剩余元素个数。现在要求你将一个长度为 n ( 1 ≤ n ≤ 1 0 5 ) n(1\leq n\leq 10^5) n(1≤n≤105)的数组a拆分成两个，但不能破坏其相对位置。 例如 a = [ 1 , 2 , 3 , 4 , 5 , 6 ] a=[1,2,3,4,5,6] a=[1,2,3,4,5,6]， a ( 0 ) = [ 1 , 3 , 5 , 6 ] a_{(0)}=[1,3,5,6] a(0)​=[1,3,5,6]和 a ( 1 ) = [ 2 , 4 ] a_{(1)}=[2,4] a(1)​=[2,4]是一种可行的拆分方案。求最大可能的 s e g ( a ( 0 ) ) + s e g ( a ( 1 ) ) 。 seg(a_{(0)})+seg(a_{(1)})。 seg(a(0)​)+seg(a(1)​)。

采取贪心策略： a ( 0 ) a_{(0)} a(0)​的最后一个元素为 x x x， a ( 1 ) a_{(1)} a(1)​的最后一个元素为 y y y，从头往后遍历，对于第 i i i个数 a i a_i ai​，考虑将其加入 a ( 0 ) a_{(0)} a(0)​还是 a ( 1 ) a_{(1)} a(1)​。

首先有一个很显然的策略：如果 a i a_i ai​与 x , y x,y x,y中的一个相同，那么就将其加进不相同的那一个数列中。如果与两个都相同，那么随便加进哪个都无所谓。

比如 1 , 1 , 1 , 2 , 3 1,1,1,2,3 1,1,1,2,3。如果将第一个1加入数组 a ( 0 ) a_{(0)} a(0)​，那么显然将第二个1加入 a ( 1 ) a_{(1)} a(1)​是更好的选择，而第三个1无论加到哪里都不会影响结果。

唯一需要考虑的就是 x , y , a i x,y,a_i x,y,ai​都不同的情况。

比如 1 , 1 , 2 , 3 , 1 , 1 , 2 1,1,2,3,1,1,2 1,1,2,3,1,1,2。最好的策略(之一)就是 a ( 0 ) = [ 1 , 2 , 1 , 2 ] , a ( 1 ) = [ 1 , 3 , 1 ] a_{(0)}=[1,2,1,2],a_{(1)}=[1,3,1] a(0)​=[1,2,1,2],a(1)​=[1,3,1]。
当分配3的时候， a ( 0 ) = [ 1 , 2 ] , a ( 1 ) = [ 1 ] a_{(0)}=[1,2],a_{(1)}=[1] a(0)​=[1,2],a(1)​=[1]，那么显然3应该分配给 a ( 1 ) a_{(1)} a(1)​来将 a ( 1 ) a_{(1)} a(1)​中末尾的1和后面将要分配的1隔开。

但是数组a中后面待分配的还有2，2在分配3时出现在 a ( 0 ) a_{(0)} a(0)​的末尾。那么为什么选择将3分配给 a ( 1 ) a_{(1)} a(1)​呢？

这就需要权衡把 x , y x,y x,y中的哪一个和后面隔开 “更迫切” 了。

可以预处理一个数组叫 n e x t next next， n e x t [ x ] next[x] next[x]表示值 x x x下一次出现的位置。
在上例中，当分配3的时候， a ( 0 ) = [ 1 , 2 ] , a ( 1 ) = [ 1 ] a_{(0)}=[1,2],a_{(1)}=[1] a(0)​=[1,2],a(1)​=[1]， n e x t [ 1 ] = 5 , n e x t [ 2 ] = 7 next[1]=5,next[2]=7 next[1]=5,next[2]=7，所以考虑用3先将1隔开。

以上的“哪一个更迫切”只是便于理解的说法，官方题解通过分类讨论给出了一个严格的证明。（其实官方那边也给了Intuitive和Formal两种）