Hdu 5699 货物运输

2023-12-26 08:18

文章标签 hdu 货物运输 5699

本文主要是介绍Hdu 5699 货物运输，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

货物运输

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

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）

二分。

对于一个二分的答案mid,有|xi-l|+|yi-r|<=mid,l和r为新建道路的左右两端。

把绝对值不等式展开为4个不等式，把l和r移动到式子一端，记录另一端的四个最值，则可以判断不等式有没有解。

当mn==mx&&MN==MX&&(mn+MN)%2==1时，2*l=mn+MN，式子无解，需要特判。

2017北京网络赛 Agent Communication 同样的道理，任取一条直径，之后同这题。

#include <cstdio>
#include <iostream>
#include <string.h>
#include <string> 
#include <map>
#include <queue>
#include <deque>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <stack>
#include <iomanip>
#define mem0(a) memset(a,0,sizeof(a))
#define meminf(a) memset(a,0x3f,sizeof(a))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
const int maxn=1000005,inf=0x3f3f3f3f;  
const ll llinf=0x3f3f3f3f3f3f3f3f;   
const ld pi=acos(-1.0L);
int x[maxn],y[maxn];bool check(int m,int mid) {int i,j;int mn,mx,MN,MX;mn=MN=inf;mx=MX=-inf;for (i=1;i<=m;i++) {if (y[i]-x[i]<=mid) continue;mn=min(mn,x[i]+y[i]+mid);  mx=max(mx,x[i]+y[i]-mid);  MN=min(MN,y[i]-x[i]+mid);  MX=max(MX,y[i]-x[i]-mid);  }if (mn==mx&&MN==MX&&(mn+MN)%2==1) return false;if (mx>mn||MX>MN) return false;return true;
}int main() {int n,m;while (scanf("%d%d",&n,&m)!=EOF) {int i,l,r,mid,ans;for (i=1;i<=m;i++) {scanf("%d%d",&x[i],&y[i]);if (x[i]>y[i]) swap(x[i],y[i]);}l=0;r=n;ans=n;while (l<=r) {mid=(l+r)/2;if (check(m,mid)) ans=mid,r=mid-1; else l=mid+1;}printf("%d\n",ans);}return 0;
}

这篇关于Hdu 5699 货物运输的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！