题目: http://codeforces.com/contest/1169/problem/C
题意:
有 n 个数, 每次可以选择 k 个, 将他们 + 1 并对 m 取模. 问最少进行多少次操作, 使得序列是非递减的.
思路:
太久没刷题遭报应了. 这两天能补多少是多少吧.
二分答案. 然后看看这个序列是不是非递减的.
对于第 i 个数, 如果 $a[i]\leq prev\leq a[i]+mid$, 说明在 mid 次操作内他肯定比他前一个数要大.
当然因为取模 所以实际上还应该包括 $a[i]\leq prev+m\leq a[i]+mid$
但如果 $prev> a[i]+mid$ 说明 mid 不够大, 则 l = mid +1
否则 r = mid
要死了二分都不会了.
- //#include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #define LL long long
- #define ull unsigned long long
- #define inf 0x7f7f7f7f
- using namespace std;
- int n, m;
- const int maxn = 3e5 + 5;
- int num[maxn];
- int main()
- {
- scanf("%d%d", &n, &m);
- for(int i = 0; i <n; i++){
- scanf("%d", &num[i]);
- }
- int l = 0, r = m;
- int ans;
- while(l <r){
- bool flag = false;
- int mid = (l + r) / 2, prev = 0;
- for(int i = 0; i < n; i++){
- int x = num[i], y = num[i] + mid;
- if(x <= prev && y>= prev || x <= prev + m && y>= prev + m){
- continue;
- }
- if(prev>= x){
- flag = true;
- break;
- }
- prev = num[i];
- }
- if(flag){
- l = mid + 1;
- }
- else{
- //ans = mid;
- r = mid;
- }
- }
- printf("%d\n", l);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3078692.html