大意:求最长连续区间,最长不连续区间。
/* ID:g0feng1 LANG:C++ TASK:milk2 */ #include <iostream> #include <fstream> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <cmath> #include <map> #include <algorithm> using namespace std; FILE *fin = fopen("milk2.in", "r"); FILE *fout = fopen("milk2.out", "w"); const int maxn = 5010; const int INF = 0x3f3f3f3f; int n; int sa; struct node { int x, y; }A[maxn]; int cmpx(node a, node b) { return a.x < b.x; } int cmpy(node a, node b) { return a.y < b.y; } void read_case() { fscanf(fin, "%d", &n); for(int i = 0; i < n; i++) fscanf(fin, "%d%d", &A[i].x, &A[i].y); sort(A, A+n, cmpx); A[n].x = INF, A[n].y = INF; } int cal_max() { int ans; int res = 0; for(int i = 0; i < n; i++) { int ans = A[i].y - A[i].x; int y = A[i].y; for(int j = i+1; j < n; j++) { if(y >= A[j].x) { if(y < A[j].y) { ans += A[j].y-y; y = A[j].y; } } } res = max(ans, res); } return res; } int cal_min() { sort(A, A+n, cmpy); int ans = 0; int x = A[n-1].x; for(int i = n-2; i >= 0; i--) { if(x > A[i].y) { int t = x - A[i].y; ans = max(ans, t); } else if(A[i].x < x) x = A[i].x; } return ans; } void solve() { read_case(); int maxv = cal_max(), minv = cal_min(); fprintf(fout, "%d %d\n", maxv, minv); } int main() { solve(); return 0; }