【題解】ZeroJudge f160: 1. 音檔剪輯

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int t, n, a, dp[10005];
vector <int> v;

int main() {
    cin >> t >> n;
    v.push_back(0);
    for (int i = 1; i <= n; i++){
        cin >> a;
        v.push_back(a);
        dp[i] = dp[lower_bound(v.begin(), v.end(), a-t)-v.begin()]+1;
    }
    cout << dp[n] << "\n";
}

while True:
    try:
        t, n = map(int, input().split())
        A = list(map(int, input().split()))
        pre = 0 #紀錄前一個切開點
        cnt = 0 #紀錄累積切點數目
        for i  in range(n):
            if A[i] - pre > t:
                pre = A[i-1]
                cnt += 1
                #print(f"cut @ {A[i]}")
            elif A[i] - pre == t:
                pre = A[i]
                cnt += 1
                #print(f"cut @ {A[i]}")
        
        if pre != A[n-1]:
            cnt += 1
        print(cnt)
    except:
        break