1402?最大值? 題目來源：?TopCoder 基準時間限制：1?秒 空間限制：131072?KB 分值:?20?難度：3級算法題 ?收藏 ?關注 一個N長的數組s[](注意這里的數組初始下標設為1，而不是0，即N個元素為s[1],s[2],...,s[N])，滿足以下性質：
1）每個元素都是非負的整數，且s[1]=0；
2）任意兩個相鄰元素差值的絕對值不大于1，即| s[i]-s[i+1] |<=1；
3）對于部分特殊點xi，要求s[xi]<=ti（這樣的特殊點一共M個）；
問在以上約束下s[]中的最大值最大可能是多少？ Input 多組測試數據，第一行一個整數T，表示測試數據數量，1<=T<=5 每組測試數據有相同的結構構成： 第一行兩個整數N，M，表示s[]的長度與特殊點的個數，其中1<=N<=100000,0<=M<=50. 之后M行，每行兩個整數xi與ti，其中1<=xi<=N,0<=ti<=100000，且xi以增序給出。 Output 每組數據一行輸出，即數組的可能最大值。 Input示例 3 10?2 3?1 8?1 100000?0 2718?5 1?100000 30?100000 400?100000 1300?100000 2500?100000 Output示例 3 99999 2717

nm算法可以過。先初始化a[i] = i-1 ,每輸入一個一個xi 和 ti 就更新下a數組。當然也有O(n)和O(m)算法， 1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 1e5+10; 4 int a[N], t, n, m, xi, ti; 5 int main() { 6 ios::sync_with_stdio(false); 7 cin >> t; 8 while(t--) { 9 cin >> n >> m; 10 for(int i = 1; i <= n; i ++) a[i] = i-1; 11 for(int i = 0; i < m; i ++) { 12 cin >> xi >> ti; 13 if(ti >= xi-1) continue; 14 if(a[xi] > ti) { 15 int j = 0; 16 while(xi+j <= n) { 17 if(a[xi+j] > ti+j) { 18 a[xi+j] = ti+j; 19 } 20 j++; 21 } 22 j = 1; 23 while(xi-j >= 1) { 24 if(a[xi-j] > ti+j) { 25 a[xi-j] = ti+j; 26 } 27 j++; 28 } 29 } 30 } 31 int MAX = -1; 32 for(int i = 1; i <= n; i ++) MAX = max(MAX, a[i]); 33 printf("%d\n",MAX); 34 } 35 return 0; 36 }

?

轉載于:https://www.cnblogs.com/xingkongyihao/p/8980747.html

總結

以上是生活随笔為你收集整理的51nod 1402最大值的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。