Codeforce 1491C Pekora and Trampoline（思维+差分）
原创
文章标签 #define #include ios 文章分类 Hadoop 大数据
©著作权归作者所有：来自51CTO博客作者为最后的荣光的原创作品，请联系作者获取转载授权，否则将追究法律责任
题目链接
题目大意： 有n个跳床，每个跳床有一个跳的距离，每个跳床跳一次就会使得弹跳距离减1，弹跳距离max(1,a[i])。你可以选择任意跳床选择开始，问你最少经过几个轮回才能将所有跳床弹跳距离都变成1。
思路： 差分维护
首先我们要将全部都转化成1，那么最优的方法就是从第一个大于1的弹床开始跳，这样一定是最优的。我们假设第一个是a[i]，那么他第一次跳到(i+a[i])上，第二次跳到(i+a[i]-1)…知道最后一次从i点开始跳就跳到(i+2)上。一共跳了(a[i]-1)次。
关注这个地方：其实就是往这个地方积累，往这个地方跳。
[En]
Pay attention to this place: in fact, it is to accumulate and jump to this place.
if(tmp<1) { if(i+1n) { b[i+1]+=(1-tmp);///会前面变1走的次数 } if(i+2n) { b[i+2]-=(1-tmp);///后端维护了 }}
#include
#include
#include
#include
#include
#include
#include
#include
#include
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
typedef pair<ll,ll> pii;
#define
#define
#define
#define
#define
#define
const int maxn=2e5+10;
#define
#define
#define
const int mod=1e9+7;
const int MOD=1e9+7;
inline int read() {
int x=0;
bool t=false;
char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch'9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
ll n,m,d;
ll a[maxn],b[maxn];
ll ans;
string str;
int main() {
ll t;
cin>>t;
while(t--) {
cin>>n;
for(int i=1; in; i++) {
scanf("%lld",&a[i]);
b[i]=0;
}
ans=0;
for(int i=1; in; i++) {
b[i]+=b[i-1];///积累贡献
///cout<
ll tmp=a[i]-b[i];///是否还需要跳
if(tmp>1) ans+=tmp-1;///需要
if(a[i]>1) {
if(i+2n) {///最后一次跳
b[i+2]++;///维护差分
}
if(i+a[i]+1n) {
b[i+a[i]+1]--;///维护差分
}
}
if(tmp<1) {
if(i+1n) {
///cout<
///cout<
b[i+1]+=(1-tmp);///会前面变1走的次数
///cout<
}
if(i+2n) {
///cout<
///cout<
b[i+2]-=(1-tmp);///后端维护了
///cout<
}
}
}
printf("%lld\n",ans);
}
return 0;
}
- 赞
- 收藏
- 评论
- *举报
上一篇：Codeforces G. Old Floppy Drive(二分+数学)
下一篇：BFS,DFS
Original: https://blog.51cto.com/u_15719209/5474548
Author: 为最后的荣光
Title: Codeforce 1491C Pekora and Trampoline（思维+差分）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/508455/
转载文章受原作者版权保护。转载请注明原作者出处！