読者です 読者をやめる 読者になる 読者になる

UVa12321 Gas Station

解法
ソートして、O(N) 程度の貪欲。

反省
入力で [ max(0, X-R), min(L, X+R) ] と端を切る処理が抜けていたためずっとTLEしてた。

int L, G;

int solve(vector<pair<int, int>>& vec) {
  int l = 0, r = 0;
  int idx = 0;
  int cnt = 0;
  while(1) {
    while(1) {
      if(G <= idx || l < vec[idx].first) break;
      r = max(r, vec[idx].second);
      idx++;
    }
    l = r;
    cnt ++;
    if( r >= L ) break;
    if(idx >= G) break;
  }
  
  if( r < L ) return -1;
  return cnt;
}

int main() {
  while(cin >> L >> G && (L|G) ) {
    vector<pair<int, int>> vec;
    for(int i=0; i<G; i++) {
      int X, R; cin >> X >> R;
      vec.push_back(make_pair(max(0, X-R), min(X+R, L)));
    }
    sort(vec.begin(), vec.end());
    if(vec[0].first > 0) { cout << -1 << endl; continue; }
    int res = solve(vec);
    if(res == -1) cout << -1 << endl;
    else cout << G-res << endl;
  }
  
  return 0;
}