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