Peking University Online Judge 2376 Cleaning Shifts
これとんでもない回数WA出したんですけど、何故だと思います?
N = 2, T = 10, C = {(1, 5), (5, 10)} のケースは成立するけど、 N = 2, T = 10, C = {(1, 5), (6, 10)} のケースは成立しないと思ってたんですよ。
社会人ならシフト替わりの引継ぎなんか常識じゃないですか(お前競プロ向いてねえわ)
#include<cstdio> #include<algorithm> using namespace std; static const int MAX_N = 25000; struct Range{int start; int end;}; int N, T; Range c[MAX_N]; bool comp(const Range &a, const Range &b){ return a.start < b.start; } int main(){ scanf("%d %d", &N, &T); for(int i = 0; i < N; i++){ scanf("%d %d", &c[i].start, &c[i].end); } sort(c, c + N, comp); int res = 0; int s = 0; for(int i = 0; i < N; i++){ s++; if(s < c[i].start){ printf("-1\n"); return 0; } int next_s = c[i].end; while(c[i + 1].start <= s && i < N){ i++; next_s = max(next_s, c[i].end); } res++; s = next_s; if(s == T) break; } if(s != T) printf("-1\n"); else printf("%d\n", res); return 0; }