Individual Training 29/06/2010

F - PKU 1065 Wooden Sticks

給定 N 組數 (a_i, b_i), 每次用一個 cost 可以 cover 一條 sequence 且每項的 (a_i, b_i) 都小於之後的那項, 問 min cost


首先很直觀的想到用greedy, sort by (a,b), 然後順著做, 如果未被 cover 就拎, 再順序掃後面的, 拎到就拎

這個greedy是對的, 時間O(N²)



後來學到 O(N lg N) 的做法, 方法也是 sort by (a,b), 然後找 b 的 longest decreasing sequence!

想一想也發現是很合理, 條 LDS 的每一項就是代了每條 sequence 最尾的那個 object
由於搵 LDS (LIS) 可以 O(N lg N), 整體也是 O(N lg N)





D - PKU 2036 I Conduit!

給定平面上 N 條線段 (input 準確至小數後兩位), 問合併哂 overlap 的後實際上有幾多條線段


其實呢個係做ctli在hkoj上的The keep都有寫過, 方法是把所有segment sort by

1. 斜率
2. y - 截距
3. x1 值 (設 x1<x2)

之後順序判斷+合併就是了, 要注恴的是無限slope的segment

由於見input只去到小數後兩位, 明顯地可以純整數咁做 (記分數form), 由於我用左

scanf("%d.%d",&x,&y);
p=x*100+y;

去食input


WA 兩棍後才發現我會將例如 3.05 和 3.5 都化作 305

頗深刻的bug