【Codeforces 924C】Riverside Curio
Codeforces
2023-09-14 09:03:44 时间
【链接】 我是链接,点我呀:)
【题意】
【题解】
设第i天总共的线数为t[i] 水平线上线数为m[i]是固定的 水平线下的线数设为d[i] 则d[i]+m[i]+1=t[i] 也就是说问题可以转化为使得t[i]最小 我们可以列出关于t[i]的不等式 t[i]= max{t[i-1],m[i]+1} ···① t[i]+1>=t[i+1] ,因为每天最多划一条线 ····② 对于①式,直接顺推就好 对于②式 我们用t[i]>=t[i+1]-1逆推 只要t[i]【代码】
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
int n;
int m[N+10],t[N+10],d[N+10];
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin >> n;
for (int i = 1;i <= n;i++) cin >> m[i];
for (int i = 1;i <= n;i++){
t[i] = max(t[i-1],m[i]+1);
}
for (int i = n-1;i >= 1;i--){
//t[i]+1>=t[i+1]
//t[i]>=t[i+1]-1
if (t[i]<t[i+1]-1){
t[i] = t[i+1]-1;
}
}
for (int i = 1;i <= n;i++){
d[i] = t[i]-m[i]-1;
}
long long ans = 0;
for (int i = 1;i <= n;i++){
ans = ans + d[i];
}
cout<<ans<<endl;
return 0;
}
="">
相关文章
- CodeForces - 557B Pasha and Tea (模拟)
- codeforces MUH and Cube Walls
- 【Codeforces 478C】Table Decorations
- 【Codeforces 63C】Bulls and Cows
- 【Codeforces Round #505 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final) B】Weakened Common Divisor
- 【31.58%】【codeforces 719B】 Anatoly and Cockroaches
- 【50.49%】【codeforces 731B】Coupons and Discounts
- 【codeforces 527D】Clique Problem
- 【codeforces 777B】Game of Credit Cards
- 【codeforces 801B】Valued Keys
- 【Codeforces Round #427 (Div. 2) C】Star sky
- CodeForces 228D. Zigzag(线段树暴力)
- Codeforces Round #265 (Div. 1)
- Codeforces Round #305 (Div. 2) D. Mike and Feet