HDU 5699 货物运输 (二分 + 不等式判断好题)

本文主要是介绍HDU 5699 货物运输 (二分 + 不等式判断好题)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

货物运输

Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 17 Accepted Submission(s): 3

Problem Description

公元2222年，l国发生了一场战争。
小Y负责领导工人运输物资。
其中有

m 种物资的运输方案，每种运输方案形如

li,ri 。表示存在一种货物从

li 运到

ri 。
这里有

n 个城市，第

i 个城市与第

i+1 个城市相连（这里

1 号城市和

n 号城市并不相连），并且从

i 号城市走到

i+1 号或者从

i+1 号走到

i 号需要耗费1点时间。
由于高科技的存在，小Y想到了一种节省时间的好方案。在X号城市与Y号城市之间设立传送站，只要这么做，在X号城市走到Y号城市不需要耗费时间，同样的，从Y号城市走到X号城市也不需要耗费时间。
但是为了防止混乱，只能设立这么一条传送站。
现在这些运输方案同时进行，小Y想让最后到达目的地的运输方案时间最短。
在样例中，存在两条运输方案，分别是1号城市到3号与2号到4号，那么我们在2号城市与3号城市建立传送站，这样运输方案时间最长的只需要1点时间就可以了。

Input

多组测试数据

第一行两个整数

n,m(1≤n,m≤1000000) 。
接下来

m 行，每行两个整数

li,ri(1≤li,ri≤n) 。（若

li=ri ，则不需要耗费任何时间）

Output

一个数表示答案。

Sample Input

  5 2
1 3
2 4

Sample Output

Source

2016"百度之星" - 初赛（Astar Round2B）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5699

题目分析：是一道二分的好题，其实从题面可以看出二分的意思，要求的是最小中的最大，但是比赛的时候没有想到怎么判断，巧妙就巧妙在判断这，首先二分答案mid，然后对于每个点对，本身距离小于等于mid的不用管，对距离大于mid的点对，我们要设一个传送站，现在就是要判断是不是所有大于mid的点对通过传送站花费都能小于等于mid，那么假设传送站的两个端点为x，y (x <= y)，对于第i个距离大于mid的点对有不等式：|li - x| + |ri - y| <= mid，将这个不等式展开并变形得到：
li - x + ri - y <= mid     =>     li + ri - mid <= x + y   =>    li + ri - mid <= x + y    1)
li - x + y - ri <= mid     =>     li - ri - mid <= x - y     =>    ri - li + mid >= y - x     2)
x - li + ri - y <= mid     =>    -li + ri - mid <= y - x    => ri - li - mid <= y - x      3)
x - li + y - ri <= mid     =>    -li - ri - mid <= -x -y    =>    ri + li + mid >= x + y    4)
明显可以看出 1)和4)是一组，2)和3)是一组，因为如果当前的传送站满足要求，则需要同时满足上面4个不等式
然后对于所有距离大于mid的，求
ma1 = max(li + ri - mid) 因为要满足所有情况，即最大的都比x+y小，后面的类似
mi1 = min(ri + li + mid)
ma2 = max(ri - li - mid)
mi2 = min(ri - li + mid)
然后合并1) 4)和2) 3)两个不等式得到mi1 >= ma1且mi2 >= ma2，这里需要注意一点，若mi1 == ma1且mi2 == ma2时，若ma1 + ma2为奇数，则还是无解，因为这个二元一次方程相加会得到2 * x = ma1 + ma2，这显然是没有整数解得需要特判这种情况，对于其他情况当前可以找到一个传送站，使m个点对连接的费用都小于等于mid
还有就是输入的时候l可能比r大，交换一下即可
给一组数据
10 4
5 10
4 9
5 9
4 10
答案：2

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const INF = 0x3fffffff;
int const MAX = 1000005;
int n, m;
int l[MAX], r[MAX];bool ok(int x)
{int mi1 = INF, ma1 = -INF, mi2 = INF, ma2 = -INF;for(int i = 0; i < m; i++){if(r[i] - l[i] > x){mi1 = min(mi1, l[i] + r[i] + x);ma1 = max(ma1, l[i] + r[i] - x);mi2 = min(mi2, r[i] - l[i] + x);ma2 = max(ma2, r[i] - l[i] - x);}}if(ma1 <= mi1 && ma2 <= mi2){if(ma1 == mi1 && ma2 == mi2){if((ma1 + ma2) & 1)return false;return true;}return true;}return false;
}int main()
{while(scanf("%d %d", &n, &m) != EOF){for(int i = 0; i  < m; i++){scanf("%d %d", &l[i], &r[i]);if(l[i] > r[i])swap(l[i], r[i]);}int le = 0, ri = n, mid, ans = 0;while(le <= ri){mid = (le + ri) >> 1;if(ok(mid)){ans = mid;ri = mid - 1;}elsele = mid + 1;}printf("%d\n", ans);}
}

这篇关于HDU 5699 货物运输 (二分 + 不等式判断好题)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！