二分法在解空间搜索：Sequence transformation

题目描述

Given sequence A={A1,A2,…,An}, it is required to change some elements in sequence A to form a strictly monotonic sequence B (strictly monotonic is defined as: Bi<Bi+1,1≤i <N).
We define the cost of the transformation from sequence A to sequence B as $cost(A,B)=max(|A_i?B_i|)(1\le i\le N)$. Please calculate the minimum cost for the transformation.
Note that each element is an integer before and after the transformation.

输入

The input contains multiple test cases. Each test case contains an integer N ($0<N<10^5$), the length of the sequence. The next line are N integers a1, a2, … , an ($0<ai<10^6,1<=i<=N$). The input terminates at the end of file (EOF).

输出

For each test case, print the minimum cost.

样例输入

5
1 4 4 4 3

样例输出

2

思路

??首先确定解的范围，下界为0，当原序列为严格递增时取0。考虑上界，本题的耗费定义为 $cost(A,B)=max(|A_i?B_i|)(1\le i\le N)$,所以我们只要考虑A序列和B序列相差最大的元素。当序列A无重复元素时，可以得出 B 1 ≥ m i n { A i ∣ 0 ≤ i ≤ n } 且 B n ≤ m a x { A i ∣ 0 ≤ i ≤ n } B_1 \geq min\{ A_i | 0\leq i \leq n \} 且 B_n \leq max\{ A_i|0\leq i \leq n \} B1?≥min{ Ai?∣0≤i≤n}且Bn?≤max{ Ai?∣0≤i≤n}这是因为，我们直接将A序列排序即可得到一个B序列，但此时不一定能使cost最小。再考虑有重复的情况，由于采用二分法cost范围对时间复杂度影响不大，可得$$0\le cost\le max(A)?min(A)+n$$ 再在这个范围里利用二分法找到最小的满足条件（只要修改基本二分查找的判断逻辑即可）。
??判断函数输入一个cost值，检查在该条件下能否令A序列变成严格单调递增的序列。采用贪心策略，从0到n依次检查每一个元素，令每一个元素再保证大于其前一个元素的基础上尽量小，若$A_i+cost\le A_{i?1}$则返回False

代码

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
int n;
long long a[100007];bool judge(long long cost)
{
    long long pre = a[0] - cost;for (int i = 1; i < n; i++){
    //令a[i]尽量小if (a[i] - cost > pre){
    pre = a[i] - cost;}else{
    if (a[i] + cost <= pre){
    return false;}pre++;}}return true;
}int main()
{
    while (~scanf("%d", &n)){
    long long max = 0;long long min = 1000000;memset(a, 0, sizeof(a));for (int i = 0; i < n; i++){
    scanf("%lld", &a[i]);if (a[i] > max) max = a[i];if (a[i] < min) min = a[i];}long long le = 0;long long ri = max - min + n;while (le <= ri){
    long long mid = le + (ri - le) / 2;if (judge(mid)){
    ri = mid - 1;}else{
    le = mid + 1;}}printf("%lld\n", le);}return 0;
}