【杭电oj】5248 - 序列变换（贪心 & 二分）

FishWang

发布于 2025-08-26 15:37:17

20100

代码可运行

运行总次数：0

代码可运行

点击打开题目

序列变换

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1039 Accepted Submission(s): 474

Problem Description

给定序列 , 要求改变序列A中的某些元素，形成一个严格单调的序列B（严格单调的定义为：）。我们定义从序列A到序列B变换的代价为。请求出满足条件的最小代价。注意，每个元素在变换前后都是整数。

Input

第一行为测试的组数 . 对于每一组：第一行为序列A的长度，第二行包含N个数， . 序列A中的每个元素的值是正整数且不超过。

Output

对于每一个测试样例，输出两行：第一行输出："Case #i:"。i代表第 i 组测试数据。第二行输出一个正整数，代表满足条件的最小代价。

Sample Input

Sample Output

   Case #1:
0
Case #2:
1

Source

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

从1 到1e6进行二分。

代码如下：

#include <cstdio>
#include <algorithm>
using namespace std;
int n;
int num[100000+11];
bool check(int x)
{
	int t = num[0] - x;
	for (int i = 1 ; i < n ; i++)
	{
		if (num[i] + x <= t)		//最大的变化还不能满足条件 
			return false;
		else if (num[i] - x > t)		//比上一个数大很多（大于t） 
			t = num[i] - x;
		else
			t++;
	}
	return true;
}
int main()
{
	int u;
	int ant = 1;
	int l,r,mid;
	scanf ("%d",&u);
	while (u--)
	{
		scanf ("%d",&n);
		for (int i = 0 ; i < n ; i++)
			scanf ("%d",&num[i]);
		l = 0;
		r = 1e6;
		printf ("Case #%d:\n",ant++);
		while (r >= l)
		{
			mid = (l + r) >> 1;
			if (check(mid))
				r = mid - 1;
			else
				l = mid + 1;
		}
		printf ("%d\n",l);
	}
	return 0;
}

网上还看到一种做法，思路上很巧妙，给一个传送门：点击打开链接

代码如下：

#include <stdio.h>

int main()
{
    int T, N, i, j, k;
    scanf("%d", &T);
    for(i = 0; i < T; i++) {
        scanf("%d", &N);
        int cost, m, bestCost = 0;
        scanf("%d", &m);
        int min = m, max = m, minJ = 0, maxJ = 0;
        for(j = 1; j < N; j++) {
            scanf("%d", &m);
            m = m - j;
            if(m <= min) {min = m; minJ=j;}
            else if(m > max) {max = m; maxJ=j;}
        }
        if(maxJ < minJ) bestCost = max - min;
        printf("Case #%d:\n", i+1);
        printf("%d\n", bestCost / 2 + bestCost % 2);
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2016-07-07，如有侵权请联系 cloudcommunity@tencent.com 删除

scanf