Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 此题大坑！要考虑目的地房间小于出发地房间的情况。。。

Posted by KatrineYang at 2016-07-08 23:03:31 on Problem 1083
```我也是醉了。
#include <iostream>
using namespace std;

class intv{
public:
int start;
int end;
intv(): start(0), end(0){}
intv(int s, int e): start(s) , end(e){}
};

int partion(intv *array, int p, int r) {
intv x = array[r];
int i = p - 1;
int j;
for (j = p; j < r; j++) {
if (array[j].start < x.start) {
i++;
intv temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
intv temp = array[j];
array[j] = array[i + 1];
array[i + 1] = temp;
return i+1;
}

void quickSort(intv *array, int p, int r) {
if (p < r) {
int q = partion(array, p, r);
quickSort(array, p, q - 1);
quickSort(array, q + 1, r);
}
}

int main() {
int cases;
cin >> cases;
for(int ii = 0; ii < cases; ii++){
int N;
intv vss[200];
cin >> N;
for(int i = 0; i < N; i++){
cin >> vss[i].start >> vss[i].end;
if(vss[i].start > vss[i].end){
int temp = vss[i].start;
vss[i].start = vss[i].end;
vss[i].end = temp;
}
}
quickSort(vss, 0, N-1);
for(int i = 0; i < N; i++){
vss[i].start -=1;
vss[i].start /=2;
vss[i].end -=1;
vss[i].end /=2;
}
bool state[200] = {false};
int remain = N;
int cnt = 0;
while(remain > 0){
int place = -1;
int idx = -1;
while(idx < N-1){
idx++;
if(state[idx] || vss[idx].start <= place){
//idx++;
continue;
}
state[idx] = true;
remain--;
place = vss[idx].end;
}
cnt++;
}
cout << cnt * 10 << endl;
}
//cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
return 0;
}
```

Followed by:

User ID:
Title:

Content: