题意是输入n和m,然后输入n个数,有一种操作每次选k个数,使得这k个数+1然后再取余m,问至少要多少次可以使这个序列变为非递减的序列。
我们可以二分操作数,然后根据贪心去改变每个数的状态,直接看代码吧不是很难理解。
#include <bits/stdc++.h> #define ll long long #define maxn 300005 using namespace std; int pre[maxn], a[maxn]; int n,m; bool Check(int x){ int y = 0; for(int i=1;i<=n;i++){ if(pre[i] <= y && pre[i] + x >= y) continue; else if(pre[i] + x >= m && pre[i] + x - m >= y) continue; else if(pre[i] + x < y) return false; else y = pre[i]; } return true; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d", &pre[i]); } int l = 0, r = 1e9, mid, ans = 0; while(l <= r){ mid = (l + r) >> 1; if(Check(mid)){ r = mid - 1; ans = mid; } else l = mid + 1; } printf("%d\n", ans); return 0; }