题目详情(修改数列):
我们有1个数列。我们可以把其中的任意1些项替换成其他的正整数,但是我们不能删掉项,也不能交换项的顺序。请问最少需要几次替换,才能把数列变成严格单调递增的?
输入格式
多组数据,每组数据第1行1个正整数n (n<=1000000)
每组数据第2行是n个空格分隔的非负整数,每一个不超过10^9,表示数列中的数。
输出格式
对每组数据,输出1行,包括其最少的替换次数。
答题说明:
输入样例
3
4 10 20
5
1 7 2 20 22
输出样例
0
1
<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循环,目前这些测试用例是可以的,但是提交后还是毛病。。。
任务还是很艰巨。。。
上一篇 jquery设置背景图片