序列变换

*Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3527 Accepted Submission(s): 1288
*

Problem Description

给定序列A={A1,A2,…,An}, 要求改变序列A中的某些元素，形成一个严格单调的序列B（严格单调的定义为：Bi<Bi+1,1≤i<N）。

我们定义从序列A到序列B变换的代价为cost(A,B)=max(|Ai?Bi|)(1≤i≤N)。

请求出满足条件的最小代价。

注意，每个元素在变换前后都是整数。

Input

第一行为测试的组数T(1≤T≤10).

对于每一组：
第一行为序列A的长度N(1≤N≤105)，第二行包含N个数，A1,A2,…,An.
序列A中的每个元素的值是正整数且不超过106。

Output

对于每一个测试样例，输出两行：

第一行输出：“Case #i:”。i代表第 i 组测试数据。

第二行输出一个正整数，代表满足条件的最小代价。

Sample Input

Sample Output

Case #1:
0
Case #2:
1

Source

2015年百度之星程序设计大赛 - 初赛(1)

题解

因为题目是求的最小代价，所以假设最小的代价是res，那么很容易得到

如果这时候的代价是在[0,res)范围之内，一定不会满足要求
如果代价在[res, 1e6] （因为题目的数据最大是1e6，所以最大到11e6即可） 之内，一定是满足要求的

根据这个来二分求解即可，需要用个check函数判断当前代价是否能满足要求（用贪心判断）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int nums[100010];
int nums1[100010];

bool check(int n, int diff){
    //贪心，第一个先最大程度的减少
    nums1[1] = nums[1] - diff;
    for(int i = 2;i <= n;++i){
        if(nums1[i] >= nums1[i-1]){
            //增大nums1[i]到刚好nums1[i-1] + 1的位置保证递增
            nums1[i] = min(max(nums1[i - 1] + 1,nums[i] - diff),nums[i] + diff);
        }else{
            //减少nums1[i]到刚好nums1[i-1] + 1的位置保证递增
            nums1[i] = max(min(nums1[i - 1] + 1,nums[i] + diff),nums[i] - diff);
        }
        if(nums1[i-1] >= nums1[i]){
            return 0;
        }
    }
    return 1;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int T;
    cin >> T;
    int tt = 1;
    while(T--){
        int n;
        cin >> n;
        for(int i = 1;i <= n;++i){
            cin >> nums[i];
        }
        //二分
        int l = 0;
        int r = 1e6;
        int mid;
        while(l < r){
            mid = (r - l) / 2 + l;
            if(check(n,mid)){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        cout << "Case #" << tt++ << ":" << endl;
        cout << l << endl;
    }
	return 0;
}