題目鏈接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1294

?

1294?修改數(shù)組? 題目來源：?HackerRank 基準時間限制：1?秒 空間限制：131072?KB 分值:?160?難度：6級算法題 ?收藏 ?關注 給出一個整數(shù)數(shù)組A，你可以將任何一個數(shù)修改為任意一個正整數(shù)，最終使得整個數(shù)組是嚴格遞增的且均為正整數(shù)。問最少需要修改幾個數(shù)？ Input 第1行：一個數(shù)N表示序列的長度(1?<=?N?<=?100000)。 第2?-?N?+?1行：每行1個數(shù)，對應數(shù)組元素。(0?<=?A[i]?<=?10^9) Output 輸出最少需要修改幾個數(shù)使得整個數(shù)組是嚴格遞增的。 Input示例 5 1 2 2 3 4 Output示例 3

?

題意：

給出一個數(shù)列，問至少修改多少個數(shù)，使得序列：全為正整數(shù)且嚴格單調(diào)遞增。

?

題解：

1.首先，不需要修改的數(shù)構成了這個數(shù)列的“骨架”，這個“骨架”且滿足：b[i].val-b[j].val>=b[i].index-b[j].index， i>j，這條不等式限制了在骨架點i和j之間，必須有足夠范圍的數(shù)。

2.可知第一個數(shù)最小為1，第二個數(shù)最小為2，……第i個數(shù)最小為i。

3.根據(jù)第2點，可以得出一個結論：當a[i]<i時，a[i]必須修改；當a[i]>=i時，a[i]可能不需要修改。

4.所以將可能不需要修改的數(shù)（包括數(shù)值和其所在的位置）提取出來，放到結構體數(shù)組b[]當中，然后求b[]數(shù)組的LIS（需滿足：b[i].val-b[j].val>=b[i].index-b[j].index， i>j），即為整個序列的“骨架”，在“骨架上”的數(shù)都不需要修改，所以：ans = n - LIS_LEN 。

?

代碼如下：

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 #include <cmath> 7 #include <queue> 8 #include <stack> 9 #include <map> 10 #include <string> 11 #include <set> 12 using namespace std; 13 typedef long long LL; 14 const int INF = 2e9; 15 const LL LNF = 9e18; 16 const int MOD = 1e9+7; 17 const int MAXN = 1e5+10; 18 19 struct node 20 { 21 int val, pos; 22 }; 23 node a[MAXN], dp[MAXN]; 24 25 bool ok(node x, node y) 26 { 27 return (x.val-y.val)>=(x.pos-y.pos); 28 } 29 30 int Search(node dp[], int n, node x) 31 { 32 int l = 1, r = n; 33 while(l<=r) 34 { 35 int mid = (l+r)>>1; 36 if(ok(x,dp[mid])) 37 l = mid + 1; 38 else 39 r = mid - 1; 40 } 41 return r; 42 } 43 44 int main() 45 { 46 int n, m; 47 while(scanf("%d", &n)!=EOF) 48 { 49 for(int i = 1; i<=n; i++) 50 scanf("%d",&a[i].val); 51 m = 0; 52 for(int i = 1; i<=n; i++) 53 if(a[i].val>=i) 54 a[++m].val = a[i].val, a[m].pos = i; 55 56 int len = 0; 57 for(int i = 1; i<=m; i++) 58 { 59 if(i==1||ok(a[i],dp[len])) 60 dp[++len] = a[i]; 61 else 62 { 63 int pos = Search(dp,len,a[i]); 64 dp[pos+1] = a[i]; 65 } 66 } 67 printf("%d\n", n-len); 68 } 69 } View Code

?

轉載于:https://www.cnblogs.com/DOLFAMINGO/p/8708500.html

總結

以上是生活随笔為你收集整理的51Nod 1294 修改数组 —— LIS的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。