AtCoder ABC 060 C - Sentou (5Q, 茶色, 300 点)

愚直シミュレーションをする問題。ただ、ある程度は計算量を知らないとドツボにハマる可能性がある。

• 問題へのリンク

問題概要

あるシャワーは、スイッチを押すとその後 秒間お湯が出る (延長するわけではない)。

時刻 (単調増加) にスイッチを押したとするとき、お湯が出ている時間は合計何秒か？

制約

• 

考えたこと

各 について、時刻 から時刻 までお湯が出たものとみなせばよい。

つまり、時刻 にスイッチを押した分の効果は、もし時刻 までお湯が出ていた場合、時刻 にスイッチを押すことによって完全に上書きされると考えるのだ。

なお、 にスイッチを押した分については 秒間流れ続ける。

この解法を素直に実装すると、 の計算量となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N, T;
    cin >> N >> T;
    vector<long long> t(N);
    for (int i = 0; i < N; i++) cin >> t[i];

    long long res = 0;
    for (int i = 0; i+1 < N; i++) res += min(T, t[i+1] - t[i]);
    res += T;
    cout << res << endl;
}