# [Platinum IV] Tågstationer [문제 링크](https://www.acmicpc.net/problem/26893) ## 문제 설명 <p>Zohan och Jimón är på väg till träningsläger i programmering. Det episka träningslägret äger rum i staden Petrozavodsk, och de har beslutat sig för att resa med tåg.</p> <p>Under resans gång så sitter Jimón av någon anledning och räknar antalet personer som går av och på vid varje station som tåget stannar vid. Dessa antal skriver han upp i sin anteckningsbok -- en stations data antecknas per sida.</p> <p>När Jimón ska kliva av tåget så ramlar han och hans anteckningsbok slits i bitar -- allt han har kvar är en hög med anteckningar huller om buller. Zohan utmanar nu Jimón att återställa ordningen i vilken stationerna uppträdde, givet siffrorna som står på sidorna som ligger på marken. Kan du hjälpa honom, eller kan du bevisa att Jimón måste ha räknat fel?</p> ## 입력 <p>På första rader står ett heltal $N$, antalet sidor i anteckningsblocket.</p> <p>Efter det följer $N$ rader (en per papperssida), vardera med två icke-negativa heltal: antalet personer som stiger på vid stationen, och antalet som stiger av.</p> <p>En person går aldrig av på samma plats som hen går på. Det garanteras att det totala antalet påstigande och det totala antalet avstigande är samma, och att detta antal är högst $10^9$. Tåget är alltid tomt när Jimón börjar räkna och tåget är alltid tomt när han har räknat klart. För enkelhets skull så antar vi att Jimón inte räknar med sig själv eller Zohan -- och det är garanterat att de går på först och stiger av sist (de missar alltså inte att räkna någon).</p> ## 출력 <p>Om det är möjligt för stationerna att ordnas på så sätt att det aldrig är fler personer som stiger av än som finns på tåget, skriv ut först en rad "<code>JA</code>", och sedan en rad med en möjlig ordning, där varje tal $1$ till $N$ förekommer exakt en gång. I annat fall, d.v.s. om Jimón gjort något fel, skriv ut "<code>NEJ</code>".</p> ## 풀이 * 버스의 사람이 점점 증가하다 감소하는 것이 그리디하기에, 타는 사람이 내리는 사람보다 많은 곳을 먼저 방문해야 한다. * 버스에 타는 사람이 내리는 사람보다 많거나 같다면, 사람의 수는 점점 증가할테니 더 적은 사람이 내리는 곳부터 방문하는 것이 그리디하다. * 버스에 타는 사람이 내리는 사람보다 적다면, 사람의 수는 점점 감소할테니 더 많은 사람이 타는 곳부터 방문하는 것이 그리디하다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; struct element { ll in, out, idx; bool operator<(const element e) const { if(in>=out) { if(e.in>=e.out) return out<e.out; return true; } else { if(e.in>=e.out) return false; return in>e.in; } } }; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<element> v(n); for(int i=0;i<n;i++) { cin >> v[i].in >> v[i].out; v[i].idx=i+1; } sort(v.begin(), v.end()); ll cur=0; for(auto e : v) { if(cur-e.out<0) { cout << "NEJ"; return 0; } cur += e.in-e.out; } cout << "JA\n"; for(auto e : v) cout << e.idx << ' '; } ```