Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //12321 - Gas Stations
- #include <iostream>
- #include <algorithm>
- #define MAX_G 10010
- using namespace std;
- int L, G, a, b;
- struct range{
- int x, y;
- range(int _x, int _y) { x = _x;
- y = _y;
- }
- range(){}
- };
- bool cmp (const range& left, const range& right){
- if (left.x == right.x) return left.y > right.y;
- return left.x < right.x;
- }
- range ranges[MAX_G];
- int main(){
- cin >> L >> G;
- do{
- for (int i = 0; i < G; ++i){
- cin >> a >> b;
- ranges[i].x = a - b;
- ranges[i].y = a + b;
- }
- sort(ranges, ranges + G, cmp);
- int maxLen = 0;
- int newMaxLen = 0;
- int deleted = 0;
- for (int i = 0; i < G; ++i) {
- while(ranges[i].x <= maxLen && i < G){
- //cout << "try " << ranges[i].x << " - " << ranges[i].y << '\n';
- newMaxLen = max(newMaxLen, ranges[i].y);
- ++i;
- }
- deleted++;
- if (newMaxLen >= L) break;
- if (newMaxLen == maxLen && maxLen < L) {
- // no solution
- //cout << "maxLen: " << maxLen << '\n';
- deleted = -1;
- break;
- } else
- --i;
- //cout << "found\n";
- maxLen = newMaxLen;
- }
- if (deleted == -1 || newMaxLen < L) cout << "-1\n";
- else
- cout << G - deleted << '\n';
- cin >> L >> G;
- } while (L > 0);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement