cf1141 E. Superhero Battle(思维)
2021/12/17 6:22:12
本文主要是介绍cf1141 E. Superhero Battle(思维),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题意:
在数组 a[]
生成的循环数组 \(a_{i+kn}=a_i\) 中,求最小的 \(j\) 使得 \(H+\sum_{i=1}^j a_i\le 0\)
思路:
这题很经典。
假设答案是 \(ans=kn+r\ \ (r<n)\),则应使 \(k\) 尽量小。维护一个前缀和最值即可。注意特判
二分找 k 也能过。
#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 2e5 + 5; ll H, a[N], n; signed main() { scanf("%lld%lld", &H, &n); ll maxx = -1e18; for(int i = 1; i <= n; i++) { //为方便,把a变负 scanf("%lld", &a[i]), a[i] = -a[i]; a[i] += a[i-1], maxx = max(maxx, a[i]); } if(a[n] <= 0) //特判 { for(int i = 1; i <= n; i++) if(a[i] >= H) { printf("%d", i); return 0; } puts("-1"); return 0; //无解 } ll k = max(0ll, (ll)ceil(1.0*(H - maxx) / a[n])); ll ans = k * n, h = k * a[n]; for(int i = 0; i <= n; i++) if(h + a[i] >= H) { ans += i; break; } printf("%lld", ans); return 0; }
这篇关于cf1141 E. Superhero Battle(思维)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享
- 2024-07-03微信支付提示订单号重复-icode9专业技术文章分享
- 2024-07-02微服务启动nacos注册上去了,但是一直没有收到请求-icode9专业技术文章分享
- 2024-07-02如何检查文件的编码格式-icode9专业技术文章分享
- 2024-07-02sublime 更改编码格式-icode9专业技术文章分享
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享