首页 > 代码库 > USACO Milk2 区间合并

USACO Milk2 区间合并

这题WA了四次,后来发现不能用所谓的桶排来写

虽然空间上是可以的,但是存在这样一个问题

比如两组数据[15,20]和[21,30]

在20 和 21这两个时刻之间没有milking,但是用桶排的方法写的话只能判断离散的量

不能判断连续的量。

 

所以这题应该要用【区间合并】的思想来写

不错的题目~

 

Souce code:

/*ID: wushuai2PROG: milk2LANG: C++*///#pragma comment(linker, "/STACK:16777216") //for c++ Compiler#include <stdio.h>#include <iostream>#include <fstream>#include <cstring>#include <cmath>#include <stack>#include <queue>#include <vector>#include <algorithm>#define ll long long#define Max(a,b) (((a) > (b)) ? (a) : (b))#define Min(a,b) (((a) < (b)) ? (a) : (b))#define Abs(x) (((x) > 0) ? (x) : (-(x)))using namespace std;const int INF = 0x3f3f3f3f;struct sc{    int s,e;}a[5011];bool cmp(struct sc a, struct sc b){    if(a.s != b.s){        return a.s < b.s;    } else{        return a.e > b.e;    }}int main() {    ofstream fout ("milk2.out");    ifstream fin ("milk2.in");    int i, j, k, t, n, m;    int ans1 = 0, ans2 = 0;    fin >> n;    for(i = 0; i < n; ++i){        fin >> a[i].s >> a[i].e;    }    sort(a, a + n, cmp);    for(i = 0; i < n - 1; ++i){        if(a[i].s == a[i + 1].s){            for(j = i + 1; j < n - 1; ++j){                a[j] = a[j + 1];            }            --n;        }    }    for(i = 0; i < n - 1; ++i){        if(a[i].e >= a[i + 1].s){            a[i].e = max(a[i].e, a[i + 1].e);            for(j = i + 1; j < n - 1; ++j){                a[j] = a[j + 1];            }            --n;            --i;        }    }    for(i = 0; i < n; ++i){        if(a[i].e - a[i].s > ans1){            ans1 = a[i].e - a[i].s;        }        if(i < n - 1 && a[i + 1].s - a[i].e > ans2){            ans2 = a[i + 1].s - a[i].e;        }    }    fout << ans1 <<   << ans2 << endl;    return 0;}

 

USACO Milk2 区间合并