A. Ekiden Race

돌아오는데 걸리는 시간이 가장 빠를 수 있는 사람의 수를 세는 문제이다.

어떤 사람이 가는데 걸리는 시간을 aia_i라고 하고 오는데 걸리는 시간을 bib_i라 하자.

i<ji < j 라면 ai<aja_i < a_j 이다.

i<ji < j 인데 ai+bi>aj+bja_i+b_i > a_j+b_j 라면 bj<bib_j < b_i 가 되기 때문에 ii는 bib_i가 가장 작을 수 없다.

그렇지 않다면 항상 가능하다.

k<ik < i 인 kk 들에 대해 aka_k 를 ∞\infty로 생각하면 bib_i 는 충분히 작을 수 있다.

k>ik > i 인 kk 들에 대해 bkb_k 를 ∞\infty로 생각하면 bib_i 는 충분히 작을 수 있다.

void solve() {
   int n;
   cin >> n;
   vi p(n);
   fv(p);
   vi mn(n);
   mn[n - 1] = p[n - 1];
   for (int i = n - 2; i >= 0; i--) mn[i] = min(mn[i + 1], p[i]);
   int ans = 0;
   for (int i = 0; i < n; i++) {
      if(mn[i] == p[i]) ans++;
   }
   cout << ans << endl;
}

Tags:

Categories:

Updated:

Comments

You may also enjoy