首页 > 代码库 > 翼支付编程大赛——修改数列
翼支付编程大赛——修改数列
题目详情（修改数列）：
我们有一个数列。我们可以把其中的任意一些项替换成其他的正整数，但是我们不能删掉项，也不能交换项的顺序。请问至少需要几次替换，才能把数列变成严格单调递增的？
输入格式
多组数据，每组数据第一行一个正整数n (n<=1000000)
每组数据第二行是n个空格分隔的非负整数,每个不超过10^9，表示数列中的数。
输出格式
对每组数据，输出一行，包含其最少的替换次数。
答题说明:
输入样例
3
4 10 20
5
1 7 2 20 22
输出样例
0
1
先说下思想：借鉴最长递增子序列（LIS）的思想，添加限制条件：元素值>=元素下标；元素之间的差值>=元素下标之间的差值。
举例：A[0...8] = {2, 1, 5, 3, 6, 4, 8, 9, 7}设置两个数组：B记录最长递增子串（符合本题题意的条件下的），Pos记录子串中各元素在原数组中的下标。设置变量：len记录子串长度。
（1）从后往前找数组A，第一个满足：元素值>=下标的元素。应该为9，所以有B[0]=9, Pos[0]=7,len=1；
（2）再看9之前的元素8，先判断它是否>=下标，可知成立。再判断(B[len-1]-A[6] = 9-8) >= (1=Pos[len-1]-6)，成立，因此子串中加入元素8。那么B[0,1] = {9,8}， Pos[0,1] = {7,6}, len=2；（3）再看8之前的元素4，由于它<下标，因此直接跳过；
（4）再看4之前的元素6，它>=下标，(B[len-1]-A[4] = 8-6) >= (2 = Pos[len-1] - 4)，因此子串加入元素6，那么B[0,1,2] = {9,8,6}，Pos[0,1,2]={7,6,4}, len = 3;（5）再看6之前的元素3，>=下标，6-3>=1，那么B[0,1,2,3]={9,8,6,3}，Pos[0,1,2,3]={7,6,4,3},len=4；（6）再看3之前的5，>=下标，不符合3-5>=1，由于5>3，得看是否要取代B中已有的元素。在B中从后往前找到，刚好大于5的数，那就是6。接下来就要判断是否应该让5来取代6后面的元素3的位置。由于6-5=1>=(2=Pos[2]-2)不成立，因此不能让5来替换，所以还是跳过；
（7）再看5之前的1，均符合要求，于是B[0,1,2,3,4]={9,8,6,3,1}，Pos[0,1,2,3,4]={7,6,4,3,1},len=5；（8）再看1之前的2，>=下标，不符合1-2>=1，由于2>1，得看是否要取代B中已有元素。同样找到3，由于3-2>=3不成立，所以跳过。
至此，得到符合要求的最长不需要改动的子串，那么元数组总长度—len就是最少需要替换的个数。
要求用java，基本输入输出也不会，只得求助百度了，下面是小菜鸡的代码：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n;
int[] num;
while(in.hasNext()){
n = in.nextInt();
num = new int[n];
for(int i = 0; i < n; i++)
num[i] = in.nextInt();
lis(num, n);
}
}
private static void lis(int[] num, int n) {
// TODO Auto-generated method stub
int[] bnum = new int[n];
int[] bpos = new int[n];
int init; //从后到前，第一个元素值大于等于下标（从0开始）的元素为首
int len; //最长严格单调子串长度
for(init = n - 1; init >= 0; init--){
if(num[init] >= init){
bnum[0] = num[init];
bpos[0] = init;
break;
}
}
len = 1;
if(init < 0){
System.out.println(n-1);
}
for(int i = init - 1; i >= 0; i--){
if(num[i] >= i){ //值大于等于下标才有比较的意义
if(bnum[len - 1] - num[i] >= bpos[len - 1] - i){
//值的差大于等于下标的差才可以添加
bnum[len] = num[i];
bpos[len++] = i;
}else if(num[i] > bnum[len - 1]){
int pos = find(bnum, bpos, len, num[i], i);
//寻找替换位置
if(pos != -1){
bnum[pos] = num[i];
bpos[pos] = i;
}
}
}
}
System.out.println(n-len);
}
private static int find(int[] bnum, int[] bpos, int len, int number, int pos) {
// TODO Auto-generated method stub
int i = 0;
for(i = len - 1; i > 0; i--){ //找到刚好比number大的元素位置
if(bnum[i - 1] > number){
break;
}
}
if(i <= 0)
return 0;
else{
if(bnum[i - 1] - number >= bpos[i - 1] - pos) //判断替换可行否
return i;
else
return -1;
}
}
}
本地测试的结果都是正确的，但是提交了是错误，实在不知道哪里的问题。。。
4
5 4 3 2
3
6
5 6 3 7 4 8
4
6
5 6 4 7 3 8
4
6
5 6 3 4 7 8
2
6
5 6 4 3 7 8
3
6
1 2 3 4 5 6
0
翼支付编程大赛——修改数列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。