| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:此题大坑!要考虑目的地房间小于出发地房间的情况。。。In Reply To:此题大坑!要考虑目的地房间小于出发地房间的情况。。。 Posted by:KatrineYang at 2016-07-08 23:03:31 > 我也是醉了。
> #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: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator