【数学】D:石子游戏 | 2021牛客寒假算法基础集训营 5
石子游戏
https://ac.nowcoder.com/acm/contest/9985/D
补充
CSDN 阅读体验更佳:【训练题35:数学】D:石子游戏 | 2021牛客寒假算法基础集训营 5
【题意】D:石子游戏 | 2021牛客寒假算法基础集训营 5
- 一排,有 个石头堆,第 堆有 个石头。
给你一个 。
你每次可以选择相邻的 个石头堆,进行一次操作,这 堆,每堆石头个数都会**增加**
问你最少操作个数使得每堆石头个数都相同,或者输出 表示不可能。【范围】
- 样例组数
【思路】赛内
- 我感觉不是直接二分+贪心就能做好的,因为假设最后每堆石头个数都是
可能 是可以达成的,但是 与 都是无法达成的,比较棘手。
于是我就对 进行了分析:
例子:
我们已经假设最终每堆都有 个石头了,那么由于第一堆增加到 的方案只有一种,就是选择增加 堆,每堆增加 个,于是变成了:重复下去。第二堆石头需要增加 个,增加方案也只有一种,就是 堆每堆增加 个。
我们从头到尾来一遍:可以看到,有解的情况就是 ,即**剩下下标从 的所有数字都相同。**
当然还有一些特殊情况,比如:这样我们操作完之后,。这个时候,我们的解就是原来序列的元素的最大值。
我们得到了 之后,就能知道增加了多少个石头,然后每次操作是增加 个,做个除法就行。 - 那么问题来了,我们代码里面怎么去设自变量 ?
额,随便给一个大的常量就行了。 给小常量是不行的,因为这样比如可能导致上面例子中的 ,然后差分增加数字会比较麻烦。 - 我怎么知道当前位置为 还是某个数字增加了一些值后的新值?
可以看到,一定是每 个数字一起变成 的,我们记录一下 表示第一位非 的位置即可。【代码】
- 时间复杂度: 记得用差分处理区间增加
_ __ __ _ _ | | \ \ / / | | (_) | |__ _ _ \ V /__ _ _ __ | | ___ _ | '_ \| | | | \ // _` | '_ \| | / _ \ | | |_) | |_| | | | (_| | | | | |___| __/ | |_.__/ \__, | \_/\__,_|_| |_\_____/\___|_| __/ | |___/ const int MAX = 1e5+50; ll aa[MAX]; ll de[MAX]; ll aim = (ll)2e9; int main() { int T;scanf("%d",&T); while(T--){ ll mx = 0; int n,k;scanf("%d%d",&n,&k); for(int i = 0;i <= n + 1;++i)de[i] = 0; for(int i = 1;i <= n;++i){ scanf("%lld",&aa[i]); mx = max(mx,aa[i]); } bool can = true; ll now = 0; int last = 0; for(int i = 1;i + k - 1 <= n;++i){ // 算前面的区间都要变成 aim now += de[i]; ll shu = aa[i] + now; if(shu > aim){ can = false; break; }else if(shu < aim){ de[i+1] += aim - shu; de[i+k] -= aim - shu; if(i > last) last = i + k - 1; } } ll ans = -1; if(last){ for(int i = n - k + 2;i <= last;++i){ // 这些数字必须都是 aim now += de[i]; ll shu = aa[i] + now; if(shu != aim){ can = false; break; } } for(int i = last + 1;i <= n;++i){ // 这些都是常数,常数都要相同 now += de[i]; ll shu = aa[i] + now; if(ans == -1)ans = shu; else if(ans != shu){ can = false; break; } } } if(!can)puts("-1"); else { if(ans == -1)ans = mx; ll cha = 0; for(int i = 1;i <= n;++i){ cha += ans - aa[i]; } cha /= k; printf("%lld\n",cha); } } return 0; }