首页 > 代码库 > Ski-Trails for Robots
Ski-Trails for Robots
Ski-Trails for Robots
Time limit: 1.0 second
Memory limit: 64 MB
Memory limit: 64 MB
One of the stages of the Robot Cross-Country World Cup was held at the Uktus Ski Lodge in Yekaterinburg.
Professor Popov‘s laboratory sent its newest Robot NS6 to take part in the race. The neural networks of this robot were well-trained in the classic style skiing. The robot was not very lucky with the drawing: he was one of the last racers to start and the trails had been already heaped up with the participants who hadn‘t been able to make their way to the finish. This created a serious problem, as the robot now had to keep switching between the ski trails in order to skirt the obstacles. As a result, it lost the precious time because moving to an adjacent trail each time took one second.
Given the places where the fallen robots lie, determine the optimal way to skirt them all in the minimum time.
Input
The first line contains integers n, s, and k separated with a space (2 ≤ n ≤ 105; 1 ≤ s ≤ n; 0 ≤ k ≤ 105). There are n parallel ski trails that lead from start to finish. They are numbered successively from 1 to n. Robot NS6 starts along the trail with number s. The integer k is the number of robots which fell down on the trails.
The following k lines describe the lying robots in the order from start to finish. In each line there are integers l and r, which mean that a robot blocked the trails with numbers from l to rinclusive (1 ≤ l ≤ r ≤ n). You can assume that all the fallen robots lie at a sufficient distance from each other (and from the start) so that Robot NS6 can perform the necessary maneuvers. If some robot blocks an outermost trail, it can be skirted on one side only. No robot blocks all the trails simultaneously.
Output
Output the minimum time in seconds that Robot NS6 spent for switching from trail to trail in order to skirt all the fallen contestants and successfully complete the race.
Sample
input | output |
---|---|
5 3 22 51 4 | 6
|
分析:参考http://blog.csdn.net/xcszbdnl/article/details/38494201;
对于当前障碍物,在障碍物旁边的点必然是可到达的最短的路程的点;
代码:
#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <climits>#include <cstring>#include <string>#include <set>#include <map>#include <queue>#include <stack>#include <vector>#include <list>#define rep(i,m,n) for(i=m;i<=n;i++)#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)#define mod 1000000007#define inf 0x3f3f3f3f#define vi vector<int>#define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)#define pii pair<int,int>#define Lson L, mid, rt<<1#define Rson mid+1, R, rt<<1|1const int maxn=1e5+10;const int dis[4][2]={{0,1},{-1,0},{0,-1},{1,0}};using namespace std;ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p%mod;p=p*p%mod;q>>=1;}return f;}int n,m,k,t,s;set<int>p,q;set<int>::iterator now,pr,la;ll dp[maxn];int main(){ int i,j; scanf("%d%d%d",&n,&s,&k); rep(i,0,n+1)dp[i]=1e18; p.insert(0),p.insert(n+1),p.insert(s); dp[s]=0; while(k--) { int a,b; scanf("%d%d",&a,&b); if(a>1) { a--; p.insert(a); now=p.find(a); pr=--now; ++now; la=++now; --now; if(dp[*now]>dp[*pr]+(*now)-(*pr))dp[*now]=dp[*pr]+(*now)-(*pr); if(dp[*now]>dp[*la]+(*la)-(*now))dp[*now]=dp[*la]+(*la)-(*now); a++; } if(b<n) { b++; p.insert(b); now=p.find(b); pr=--now; ++now; la=++now; --now; if(dp[*now]>dp[*pr]+(*now)-(*pr))dp[*now]=dp[*pr]+(*now)-(*pr); if(dp[*now]>dp[*la]+(*la)-(*now))dp[*now]=dp[*la]+(*la)-(*now); b--; } q.clear(); for(now=p.lower_bound(a);now!=p.end()&&*now<=b;now++)q.insert(*now); for(int x:q)p.erase(x),dp[x]=1e18; } ll mi=1e18; rep(i,1,n)if(mi>dp[i])mi=dp[i]; printf("%lld\n",mi); //system("pause"); return 0;}
Ski-Trails for Robots
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。