AtCoder Regular Contest 162 - A. Ekiden Race (446)

A. Ekiden Race

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

어떤 사람이 가는데 걸리는 시간을 $a_i$라고 하고 오는데 걸리는 시간을 $b_i$라 하자.

$i < j$ 라면 $a_i < a_j$ 이다.

$i < j$ 인데 $a_i+b_i > a_j+b_j$ 라면 $b_j < b_i$ 가 되기 때문에 $i$는 $b_i$가 가장 작을 수 없다.

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

$k < i$ 인 $k$ 들에 대해 $a_k$ 를 $\infty$로 생각하면 $b_i$ 는 충분히 작을 수 있다.

$k > i$ 인 $k$ 들에 대해 $b_k$ 를 $\infty$로 생각하면 $b_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;
}