hdu No.5248 序列变换(二分+贪心)

2021/7/22 6:10:04

本文主要是介绍hdu No.5248 序列变换(二分+贪心),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目链接:https://acm.dingbacode.com/showproblem.php?pid=5248

序列变换

*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

2
2
1 10
3
2 5 4

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;
}

最后,关于二分我好像想通了为什么为什么二分老是会卡在r - l == 1的地方死循环,

  • 如果下面是l = midr = mid - 1的话,求mid应该是mid = (l - r) / 2 + r
  • 如果下面是l = mid + 1r = mid的话,求mid应该是mid = (r - l) / 2 + l


这篇关于hdu No.5248 序列变换(二分+贪心)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程