程序员人生 网站导航

翼支付编程大赛――修改数列

栏目:php教程时间:2014-12-18 09:02:19

题目详情(修改数列):

我们有1个数列。我们可以把其中的任意1些项替换成其他的正整数,但是我们不能删掉项,也不能交换项的顺序。请问最少需要几次替换,才能把数列变成严格单调递增的?

输入格式

多组数据,每组数据第1行1个正整数n (n<=1000000)

每组数据第2行是n个空格分隔的非负整数,每一个不超过10^9,表示数列中的数。

输出格式

对每组数据,输出1行,包括其最少的替换次数。

答题说明:

输入样例  

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,第1个满足:元素值>=下标的元素。应当为9,所以有B[0]=9, Pos[0]=7,len=1;
(2)再看9之前的元素8,先判断它是不是>=下标,可知成立。再判断(B[len⑴]-A[6] = 9⑻) >= (1=Pos[len⑴]⑹),成立,因此子串中加入元素8。那末B[0,1] = {9,8}, Pos[0,1] = {7,6}, len=2;
(3)再看8之前的元素4,由于它<下标,因此直接跳过;
(4)再看4之前的元素6,它>=下标,(B[len⑴]-A[4] = 8⑹) >= (2 = Pos[len⑴] - 4),因此子串加入元素6,那末B[0,1,2] = {9,8,6},Pos[0,1,2]={7,6,4}, len = 3;
(5)再看6之前的元素3,>=下标,6⑶>=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⑸>=1,由于5>3,得看是不是要取代B中已有的元素。在B中从后往前找到,恰好大于5的数,那就是6。接下来就要判断是不是应当让5来取代6后面的元素3的位置。由于6⑸=1>=(2=Pos[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⑵>=1,由于2>1,得看是不是要取代B中已有元素。一样找到3,由于3⑵>=3不成立,所以跳过。
至此,得到符合要求的最长不需要改动的子串,那末元数组总长度―len就是最少需要替换的个数。
要求用java,基本输入输出也不会,只得求助百度了,下面是小菜鸡的代码:
<pre name="code" class="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();
            int len = 0;
            for(int i = n; i > 0; i--){//暴力破解!!
            	int tmp = lis(num, i);
            	len = tmp > len ? tmp : len;
            }
            System.out.println(n-len);
        }
    }  
  
    private static int lis(int[] num, int n) {
		// TODO Auto-generated method stub
		int[] bnum = new int[n];
		int[] bpos = new int[n];
		int init;	//从后到前,第1个元素值大于等于下标(从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){
			return 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 != ⑴){
						bnum[pos] = num[i];
						bpos[pos] = i;
					}
				}
			}
		}
		return 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 ⑴;
		}
	}
}



本地测试的结果都是正确的,但是提交了是毛病,实在不知道哪里的问题。。。
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
1 3 3 2 4
3


简单修改下,增加了个暴力破解的for循环,目前这些测试用例是可以的,但是提交后还是毛病。。。

任务还是很艰巨。。。


------分隔线----------------------------
------分隔线----------------------------

最新技术推荐