ABC 024 B - 自動ドア
問題概要
省略
解法
aは昇順に並んでいるので、時系列に沿った形で見ていく。ドアが開き始めた時間をl、閉じる予定の時間をrおき、aiがrより小さいなら、なら、時間がtよりすくないが延長され、rより大きいなら、一度ドアが閉じ、そのあと、時間がtだけ延長される。これを実装する。直近のドアが開いた時間と閉じる予定の時間だけを持っておけばいい。
ミス
下手に実装すると大変そう。
コード
#include <iostream> #include <cstdio> #include <set> #include <vector> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) int main(void){ int n, t; cin >> n >> t; int a[100010]; rep(i, n) cin >> a[i]; ll ans = 0; //lは開き始めた時間 rはドアが閉じる時間 int l = a[0], r = a[0] + t; for (int i = 1; i < n; ++i){ if(r < a[i]){//ドアがいったん締まり、また開く、 ans += r - l; l = a[i]; r = a[i] + t; }else{//ドアが開いたままで、さらに開く時間が延長 r = a[i] + t; } } ans += r - l; printf("%lld\n", ans); return 0; }