NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC國中組 » NPSC2001國中組初賽
 題目 E 撿石頭 (C++)

作者 主題: 題目 E 撿石頭 (C++)  (閱讀 840 次)

rscpp

  • 中級會員
  • ***
  • 文章數: 60
    • 檢視個人資料
題目 E 撿石頭 (C++)
« 於: 四月 14, 2015, 01:36:51 pm »

代碼: [選擇]
// npsc01-j1E (2001 國初 題目 E 撿石頭)
// 第1列 n 有n組資料,每一組第1列m為有m個數字(數字有可能為負) 
// 最長遞增子序列, 因 m高達 10^5又不需列出序列,故 m^2的方法不可行
// LIS nlogn , 此方法只可求長度,無法列出序列
// 參考 http://fanli7.net/a/bianchengyuyan/C__/20140524/507756.html
// 解法說明參考:http://tc.wangchao.net.cn/bbs/detail_59352.html

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[100005];   // 存目前為止遞增列可放入的資料
int main() {
   int n, m;
// while (~scanf("%d", &n)) {  // 若資料量太大也可能需改為scanf
   cin >> n;
   while( n-- )
   {
       cin >> m;   // 每一組資料 m 個數字(有可能負數)
       int now = 0;  // 目前的長度
       cin >>a[now];  //scanf("%d", &a[now]);
       --m;   // 第1筆
       while (m--)  // 接著第2筆之後的 
       {
          int num;
          cin >> num;   //scanf("%d", &num);
          if (num > a[now]) a[++now] = num;   // 若比目前的最後一個大,加至後面
          // 否則,在a中找到 >= num 的最左一格 放入 num
          else *lower_bound(a, a + now, num) = num;
       }
       cout << now+1 << endl;  // 因由0開始 ,長度加1 //printf("%d\n", now + 1);
   }
   return 0;
}
/*
5
5
1 2 3 4 5
5
5 4 3 2 1
7
1 9 10 5 11 2 13
2
2 -1
11
1 9 10 5 6 11 7 8 2 13 14
-------------------
5
1
5
1
7
*/

記錄
+ NPSC補完計劃 » NPSC國中組 » NPSC2001國中組初賽
 題目 E 撿石頭 (C++)