【牛客周赛 107】E 题【小苯的刷怪笼】题解
题目链接
题目大意
给定三个正整数n , a , k n, a, kn,a,k，其中：
- n nn为怪物的数量，n nn个怪物站成一排，从左到右编号1 11到n nn；
- a aa为n nn个怪物的血量和，且每个怪物的血量都是正数；
- k kk为小苯的操作次数。
每次操作，小红会选择一个或相邻两个怪物，使得它（们）的血量（各自）− 1 -1−1。当怪物的血量≤ 0 \leq 0≤0时，怪物被消灭（相邻关系不会改变）。
小红一定会选择最优策略，使用尽可能少的攻击次数消灭这些怪物。
在这种情况下，小苯希望小红能使用恰好k kk次攻击消灭所有的怪物。
请你帮小苯找出一个可能的血量分配方案，如果不行输出− 1 -1−1。
数据范围
- 1 ≤ n ≤ 2 ⋅ 1 0 5 , 1 \leq n \leq 2 \cdot 10^5,1≤n≤2⋅105,
- n ≤ a ≤ 1 0 9 , n \leq a \leq 10^9,n≤a≤109,
- 1 ≤ k ≤ 1 0 9 . 1 \leq k \leq 10^9.1≤k≤109.
Solution
首先，n = 1 n = 1n=1时，只能将a aa分配给一个怪物，所以只要看是否有a = k a = ka=k。
下面考虑n > 1 n > 1n>1的情况。
由于需要恰好k kk次操作，所以我们需要找到操作次数的上下界。
先找下界L LL。
- 要想操作次数接近下界L LL，就要尽可能让小红选择相邻两个怪物一起扣血；
- 首先为每个怪物分配1 11生命值，这样还剩下a − n a - na−n的血量和；
- 然后我们再分配⌊ a − n 2 ⌋ \left\lfloor \dfrac{a - n}{2} \right\rfloor⌊2a−n⌋给怪物1 11，分配⌈ a − n 2 ⌉ \left\lceil \dfrac{a - n}{2} \right\rceil⌈2a−n⌉给怪物2 22。
- 当n nn是偶数，
- 小红先通过n 2 \dfrac{n}{2}2n次操作消除下面分配的1 11生命值，然后再通过⌈ a − n 2 ⌉ \left\lceil \dfrac{a - n}{2} \right\rceil⌈2a−n⌉次操作消灭怪物1 11和2 22；
- 操作次数为n 2 + ⌈ a − n 2 ⌉ = ⌈ a 2 ⌉ \dfrac{n}{2} + \left\lceil \dfrac{a - n}{2} \right\rceil = \left\lceil \dfrac{a}{2} \right\rceil2n+⌈2a−n⌉=⌈2a⌉；
- 当n nn是奇数，
- 小红先通过⌈ n 2 ⌉ \left\lceil \dfrac{n}{2} \right\rceil⌈2n⌉次操作消除下面分配的1 11生命值，这时会影响到怪物2 22的血量会提前− 1 -1−1，变为⌈ a − n 2 ⌉ − 1 ≤ ⌊ a − n 2 ⌋ \left\lceil \dfrac{a - n}{2} \right\rceil - 1 \leq \left\lfloor \dfrac{a - n}{2} \right\rfloor⌈2a−n⌉−1≤⌊2a−n⌋，所以再通过⌊ a − n 2 ⌋ \left\lfloor \dfrac{a - n}{2} \right\rfloor⌊2a−n⌋次操作就能消灭怪物1 11和2 22；
- 操作次数为⌈ n 2 ⌉ + ⌊ a − n 2 ⌋ = ⌊ n + 1 2 ⌋ + ⌊ a − n 2 ⌋ = ⌊ a + 1 2 ⌋ = ⌈ a 2 ⌉ \left\lceil \dfrac{n}{2} \right\rceil + \left\lfloor \dfrac{a - n}{2} \right\rfloor = \left\lfloor \dfrac{n + 1}{2} \right\rfloor + \left\lfloor \dfrac{a - n}{2} \right\rfloor = \left\lfloor \dfrac{a + 1}{2} \right\rfloor = \left\lceil \dfrac{a}{2} \right\rceil⌈2n⌉+⌊2a−n⌋=⌊2n+1⌋+⌊2a−n⌋=⌊2a+1⌋=⌈2a⌉；
- 这样就说明操作次数下界L = ⌈ a 2 ⌉ L = \left\lceil \dfrac{a}{2} \right\rceilL=⌈2a⌉。
再找上界R RR。
- 要想操作次数接近上界R RR，就要尽可能让小红只选择一个怪物扣血；
- 首先为每个怪物分配1 11生命值，这样还剩下a − n a - na−n的血量和；
- 然后我们直接给怪物1 11分配a − n a - na−n的血量。
- 当n nn是偶数，
- 小红先通过n 2 \dfrac{n}{2}2n次操作消除下面分配的1 11生命值，然后再通过a − n a - na−n次操作消灭怪物1 11；
- 操作次数为n 2 + ( a − n ) = a − n 2 = a − ⌊ n 2 ⌋ \dfrac{n}{2} + (a - n) = a - \dfrac{n}{2} = a - \left\lfloor \dfrac{n}{2} \right\rfloor2n+(a−n)=a−2n=a−⌊2n⌋；
- 当n nn是奇数，
- 小红先通过⌈ n 2 ⌉ \left\lceil \dfrac{n}{2} \right\rceil⌈2n⌉次操作消除下面分配的1 11生命值，这时怪物1 11不受影响，还剩a − n a - na−n的血量值，我们再通过a − n a - na−n次操作消灭怪物1 11；
- 操作次数为⌈ n 2 ⌉ + ( a − n ) = a − ⌊ n 2 ⌋ \left\lceil \dfrac{n}{2} \right\rceil + (a - n) = a - \left\lfloor \dfrac{n}{2} \right\rfloor⌈2n⌉+(a−n)=a−⌊2n⌋；
- 这样就说明操作次数上界R = a − ⌊ n 2 ⌋ R = a - \left\lfloor \dfrac{n}{2} \right\rfloorR=a−⌊2n⌋。
所以只有当⌈ a 2 ⌉ ≤ k ≤ a − ⌊ n 2 ⌋ \left\lceil \dfrac{a}{2} \right\rceil \leq k \leq a - \left\lfloor \dfrac{n}{2} \right\rfloor⌈2a⌉≤k≤a−⌊2n⌋时，才有可能构造一个合法分配。
考虑从上界R = a − ⌊ n 2 ⌋ R = a - \left\lfloor \dfrac{n}{2} \right\rfloorR=a−⌊2n⌋开始调整。
此时怪物1 11除了底部的1 11血量值，还有额外分配的a − n a - na−n血量值，我们将其拿出s ss来分配给怪物2 22，这样怪物1 11的额外血量为a − n − s a - n - sa−n−s，怪物2 22的额外血量为s ss。
接着考虑这种分配下的操作次数。
- 当n nn是偶数，需要满足a − n − s ≥ s a - n - s \geq sa−n−s≥s，即s ≤ ⌊ a − n 2 ⌋ s \leq \left\lfloor \dfrac{a - n}{2} \right\rfloors≤⌊2a−n⌋；
- 小红先通过n 2 \dfrac{n}{2}2n次操作消除下面分配的1 11生命值，然后再通过a − n − s a - n - sa−n−s次操作消灭怪物1 11和2 22；
- 操作次数为n 2 + ( a − n − s ) = a − n 2 − s = a − ⌊ n 2 ⌋ − s \dfrac{n}{2} + (a - n - s) = a - \dfrac{n}{2} - s = a - \left\lfloor \dfrac{n}{2} \right\rfloor- s2n+(a−n−s)=a−2n−s=a−⌊2n⌋−s；
- 当n nn是奇数，需要满足a − n − s ≥ s − 1 a - n - s \geq s - 1a−n−s≥s−1，即s ≤ ⌊ a − n + 1 2 ⌋ = ⌈ a − n 2 ⌉ s \leq \left\lfloor \dfrac{a - n + 1}{2} \right\rfloor = \left\lceil\dfrac{a - n}{2} \right\rceils≤⌊2a−n+1⌋=⌈2a−n⌉；
- 小红先通过⌈ n 2 ⌉ \left\lceil \dfrac{n}{2} \right\rceil⌈2n⌉次操作消除下面分配的1 11生命值，这时怪物2 22受到影响，还剩s − 1 s - 1s−1的血量值，我们再通过a − n − s a - n - sa−n−s次操作消灭怪物1 11和2 22；
- 操作次数为⌈ n 2 ⌉ + ( a − n − s ) = a − ⌊ n 2 ⌋ − s \left\lceil \dfrac{n}{2} \right\rceil + (a - n - s) = a - \left\lfloor \dfrac{n}{2} \right\rfloor - s⌈2n⌉+(a−n−s)=a−⌊2n⌋−s；
综上，操作次数为a − ⌊ n 2 ⌋ − s a - \left\lfloor \dfrac{n}{2} \right\rfloor - sa−⌊2n⌋−s。
于是令k = a − ⌊ n 2 ⌋ − s k = a - \left\lfloor \dfrac{n}{2} \right\rfloor- sk=a−⌊2n⌋−s，得到s = a − ⌊ n 2 ⌋ − k . s = a - \left\lfloor \dfrac{n}{2} \right\rfloor - k.s=a−⌊2n⌋−k.
接下来只要验证这个解是否满足条件。
- 当n nn为偶数，需要满足s ≤ ⌊ a − n 2 ⌋ s \leq \left\lfloor \dfrac{a - n}{2} \right\rfloors≤⌊2a−n⌋；
- 当a aa为偶数，左式s = a − n 2 − k s = a - \dfrac{n}{2} - ks=a−2n−k，右式a − n 2 \dfrac{a - n}{2}2a−n，作差得到a 2 − k = ⌈ a 2 ⌉ − k ≤ 0 \dfrac{a}{2} - k = \left\lceil \dfrac{a}{2} \right\rceil - k \leq 02a−k=⌈2a⌉−k≤0
- 当a aa为奇数，左式a − n 2 − k a - \dfrac{n}{2} - ka−2n−k，右式a − n − 1 2 \dfrac{a - n - 1}{2}2a−n−1，作差得到a + 1 2 − k = ⌈ a 2 ⌉ − k ≤ 0 \dfrac{a + 1}{2} - k = \left\lceil \dfrac{a}{2} \right\rceil - k \leq 02a+1−k=⌈2a⌉−k≤0；
- 当n nn为奇数，需要满足s ≤ ⌈ a − n 2 ⌉ s \leq \left\lceil\dfrac{a - n}{2} \right\rceils≤⌈2a−n⌉；
- 当a aa为奇数，左式a − n − 1 2 − k a - \dfrac{n - 1}{2} - ka−2n−1−k，右式a − n 2 \dfrac{a - n}{2}2a−n，作差得到a + 1 2 − k = ⌈ a 2 ⌉ − k ≤ 0 \dfrac{a + 1}{2} - k = \left\lceil \dfrac{a}{2} \right\rceil - k \leq 02a+1−k=⌈2a⌉−k≤0；
- 当a aa为偶数，左式a − n − 1 2 − k a - \dfrac{n - 1}{2} - ka−2n−1−k，右式a − n + 1 2 \dfrac{a - n + 1}{2}2a−n+1，作差得到a 2 − k = ⌈ a 2 ⌉ − k ≤ 0 \dfrac{a}{2} - k = \left\lceil \dfrac{a}{2} \right\rceil - k \leq 02a−k=⌈2a⌉−k≤0；
综上，解s = a − ⌊ n 2 ⌋ − k s = a - \left\lfloor \dfrac{n}{2} \right\rfloor - ks=a−⌊2n⌋−k合法。
那么额外分配给怪物1 11的为a − n − s = k − ⌈ n 2 ⌉ a - n - s = k - \left\lceil \dfrac{n}{2} \right\rceila−n−s=k−⌈2n⌉，怪物2 22的为a − ⌊ n 2 ⌋ − k a - \left\lfloor \dfrac{n}{2} \right\rfloor - ka−⌊2n⌋−k。
C++ Code
#include<bits/stdc++.h>intmain(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);intn,a,k;std::cin>>n>>a>>k;if(n==1){std::cout<<(a==k?a:-1)<<"\n";return0;}if((a+1)/2>kora-n/2<k){std::cout<<-1<<"\n";return0;}std::vectorans(n,1);ans[0]+=k-(n+1)/2;ans[1]+=a-k-n/2;for(inti=0;i<n;i++){std::cout<<ans[i]<<" \n"[i==n-1];}return0;}