首页 > 代码库 > CSDN 中国电信翼支付2014编程大赛复赛 修改数列（LIS）
CSDN 中国电信翼支付2014编程大赛复赛 修改数列（LIS）
题目意思：51nod1294
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1294
给出一个整数数组A，你可以将任何一个数修改为任意一个正整数，最终使得整个数组是严格递增的且均为正整数。问最少需要修改几个数？
Input
第1行：一个数N表示序列的长度(1 <= N <= 100000)。 第2 - N + 1行：每行1个数，对应数组元素。(0 <= A[i] <= 10^9)
Output
输出最少需要修改几个数使得整个数组是严格递增的。
Input 示例
5 1 2 2 3 4
Output 示例
3题目分析：
对于此类问题，特点在原位置的排序，我们的处理思路就是，首先每一个数减去其所在的位置，再对其进行使用LIS，但需要注意题目中要求的是正整数，所以我们必须对大于等于0的值进行LIS，修改的个数就是n-最长的LIS。
AC代码（java/c++）：
C++：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<iterator>
#define MAX 100005
using namespace std;
int a[MAX],b[MAX];
int main()
{
int n;
while(scanf("%d",&n)!=EOF){
int cnt=0;
vector<int> v;
vector<int>::iterator it;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
a[i]=a[i]-(i+1);//每一个数减去其所在位置的序号
if(a[i]>=0) b[cnt++]=a[i];
}
if(cnt==0){
cout<<n<<endl; continue;
}
v.push_back(b[0]);
for(int i=1;i<cnt;i++){
if(b[i]>=*(v.end()-1)){
v.push_back(b[i]);
}
else{
it=upper_bound(v.begin(), v.end(), b[i]);
*(it)=b[i];
}
}
//printf("%d\n",v.size());
printf("%d\n",n-v.size());
}
return 0;
}java代码：
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;
import javax.naming.BinaryRefAddr;
import javax.xml.soap.SAAJResult;
public class XUIGAI_ARRAY {
static int BinarySearch(int s[],int x,int low,int high)
{
while(low<=high)
{
int middle=(high+low)/2;
if(x<s[middle])high=middle-1;
else if(x>s[middle])low=middle+1;
else return middle;
}
return high+1;
}
public static void main(String[] args) {
int a[]=new int[1000005];
int b[]=new int[1000005];
int c[]=new int[1000005];
int n,cnt;
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
n=sc.nextInt();
cnt=0;
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
a[i]=a[i]-(i+1);
if(a[i]>=0) b[cnt++]=a[i];
}
if(cnt==0){
System.out.println(n);
continue;
}
int len=1,pos;
c[len-1]=b[0];
for(int i=1;i<cnt;i++){
// System.out.println(b[i]);
if(b[i]>=c[len-1]){
c[len++]=b[i];
}
else{
pos=BinarySearch(c, b[i], 0, len-1);
// System.out.println(pos);
if(pos>=0&&pos<=len-1) for(int j=pos;j<=len;j++){
if(c[j]>b[i]){
pos=j; break;
}
}
c[pos]=b[i];
}
}
System.out.println(n-len);
}
}
}CSDN 中国电信翼支付2014编程大赛复赛 修改数列（LIS）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。