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 |
Greedy Algorithm accepted in 0ms.#include <iostream> #include <string.h> #include <algorithm> using namespace std; const int N = 200; struct Node { int start, end; } table[N]; int res[N]; int group_cnt; int end[N]; struct less_end { bool operator()(const int a, const int b) { return table[a].end < table[b].end; } }; void get_res() { int n, s, t; cin >> n; for(int i=0; i<n; i++) { cin >> s >> t; table[i].start = min(s, t); table[i].end = max(s, t); if(table[i].start % 2 == 0) table[i].start --; if(table[i].end % 2 == 1) table[i].end ++; res[i] = i; } sort(res, res+n, less_end()); group_cnt = 0; memset(end, 0, sizeof(end)); for(int i=0; i<n; i++) { int idx = -1; int max_end = 0; for(int j=0; j<group_cnt; j++) { if(end[j] < table[res[i]].start) { if(end[j] > max_end) { max_end = end[j]; idx = j; } } } if(idx == -1) { end[group_cnt++] = table[res[i]].end; } else { end[idx] = table[res[i]].end; } } cout << group_cnt * 10 << endl; } int main() { int t; cin >> t; while(t--) { get_res(); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator