AOJ 1380 / ACM-ICPC 2017 Asia Tsukuba Regional Contest: C. Medical Checkup

,

problem

$n$人の人と可算個の機械$0, 1, 2, \dots$がある。 人々が機械を番号の順に使っていく。 人$i$は機械を使うのに時間$h_i$かかり、どの機械も同時にひとりまでしか使えない。 時刻$t$でそれぞれの人がどの機械を使っている(あるいは使えるようになるのを待機している)か答えよ。

solution

人を順番に見ていく。どの人$i$も機械$0$を時刻$a_i$に使い始めて以降は$b_i$の間隔で次の機械を使う。 よってこのふたつの値を更新しながら舐めればよい。 $O(n)$。

図:

0: 00000111112222233333444445555566666...
1:      000  111  222  333  444  555  ...
2:         000000011111112222222333333...
3:                00     11     22    ...

implementation

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
template <class T> inline void chmax(T & a, T const & b) { a = max(a, b); }

int main() {
    int n, t; scanf("%d%d", &n, &t);
    ll offset = 0, interval = 0;
    while (n --) {
        int h; scanf("%d", &h);
        chmax<ll>(interval, h);
        ll p = (t - offset) / interval;
        ll q = (t - offset) % interval;
        int result = max<ll>(0, p + (q >= h));
        printf("%d\n", result + 1);
        offset += h;
    }
    return 0;
}