Regionals 2014 >> Asia - Tokyo

题意：走过N个点到达出口，有M个约束条件，每个约束条件ci、di，di必须在ci前走，也就是说如果先走了ci那么就需要走到di后再折回来再走一遍ci（并且di是大于ci的，所以一定是要走回来的）

思路：基础步数肯定是N+1.然后我们将需要走回的最左边排序，记录当前最左边和最右边；如果当前最右边小于当前状态的左边，那么就可以把前面那些进行计算了，即步数加上当前最右边走到当前最左边的步数和再走回来的步数，当前最左边也就变成了现在的左边，当前最右边也就变成了现在的右边。注意：最后还需要再加一次哦。

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<vector>
#include<cmath>
#include<stack>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef struct node{
ll l,r;
ll i;
}node;
node no[505];
bool cmp(node x,node y){
return x.l < y.l;
}
int main(){
ll n,m;
while(~scanf("%lld%lld", &n, &m)){
for(ll i = 0;i < m;i++){
scanf("%lld%lld", &no[i].l, &no[i].r);
no[i].i = i;
}
sort(no,no+m,cmp);
ll ans = n+1;
ll t1 = -1,t2 = -1; //t1当前最左边，t2当前最右边
for(ll i = 0;i < m;i++){
if(t2 < no[i].l){
if(t1!=-1 || t2!=-1){
ans += 2*(t2-t1);
}
t1 = no[i].l;
t2 = no[i].r;
}
else if(t2 < no[i].r) t2 = no[i].r;
}
ans += 2*(t2-t1);
printf("%lldn", ans);
}
return 0;
}

最后

以上就是落后黑夜为你收集整理的Regionals 2014 >> Asia - Tokyo的全部内容，希望文章能够帮你解决Regionals 2014 >> Asia - Tokyo所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。