icpc:problems:701b_replace_and_keep_sorted
problems | |
---|---|
名称 | Replace and Keep Sorted |
题目编号 | 701B |
题目链接 | codeforces.com/… |
来源 | CodeForces |
算法分类 | 前缀和 |
难易程度 | 独立完成 |
Replace and Keep Sorted
想法
一个数的可调整范围是固定的,也就是区间的端点需要调整一下,其他都没什么问题。
代码实现
#include<cstdio>//uncle-lu 701 #include<algorithm> template<class T>void read(T &x) { x=0;int f=0;char ch=getchar(); while(ch<'0'||ch>'9') { f|=(ch=='-'); ch=getchar(); } while(ch<='9'&&ch>='0') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } x = f ? -x : x; return ; } int line[100010]; int sum[100010]; int n, q, k; int main() { read(n);read(q);read(k); for(int i=1; i<=n; ++i) read(line[i]); line[0]=0;line[n+1]=k+1; for(int i=1; i<=n; ++i) { sum[i] += sum[i-1]; sum[i] += (line[i] - line[i-1] - 1); sum[i] += (line[i+1] - line[i] - 1); } int l, r, ans; for(int i=1; i<=q; ++i) { read(l);read(r); ans = sum[r-1]-sum[l]; ans += ((line[l] - 0 - 1)+(line[l+1]-line[l]-1)); ans += ((line[r] - line[r-1] - 1)+(k+1 - line[r] - 1)); printf("%d\n", ans); } return 0; }
/app/www/public/data/pages/icpc/problems/701b_replace_and_keep_sorted.txt · 最后更改: 2023/10/01 10:45 由 温婕莺