首页 > 代码库 > 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 区间合并
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。