POJ2374,求hack
  • 板块灌水区
  • 楼主zshcchenyi
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/4/18 20:18
  • 上次更新2024/4/18 22:10:25
查看原帖
POJ2374,求hack
499463
zshcchenyi楼主2024/4/18 20:18
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e6+10;
int n,s;
int l[N],r[N];
int ans;
int fr[N],fl[N];//fr[i]表示在i点向右走的最小路径,fl [i]表示在i点向左走的最小路径
int as(int x){
	if(x<0){
		return -1*x;
	}
	return x;
}
int main(){
	scanf("%d%d",&n,&s);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&l[i],&r[i]);
	}
	fl[n]=as(s-l[n]);
	fr[n]=as(r[n]-s);
	
	for(int i=n-1;i>=1;i--){
		if(l[i+1]<=l[i]&&l[i]<=r[i+1]&&r[i+1]<=r[i]){
			if(fl[i+1]>fr[i+1]+r[i+1]-l[i]){
				fl[i]=fr[i+1]+r[i+1]-l[i];
			}else{
				fl[i]=fl[i+1];
				l[i]=l[i+1];
			}
			fr[i]=min(fl[i+1]+r[i]-l[i+1],fr[i+1]+r[i]-r[i+1]);
		}
		
		else if(l[i+1]<=l[i]&&r[i]<=r[i+1]){
			if(fl[i+1]>fr[i+1]+r[i+1]-l[i]){
				fl[i]=fr[i+1]+r[i+1]-l[i];
			}else{
				fl[i]=fl[i+1];
				l[i]=l[i+1];
			}
			if(fr[i+1]>fl[i+1]+r[i]-l[i+1]){
				fr[i]=fl[i+1]+r[i]-l[i+1];
			}else{
				fr[i]=fr[i+1];
				r[i]=r[i+1];
			}
		}
		
		else if(l[i]<=l[i+1]&&r[i+1]<=r[i]){
			fl[i]=min(fl[i+1]+l[i+1]-l[i],fr[i+1]+r[i+1]-l[i]);
			fr[i]=min(fr[i+1]+r[i]-r[i+1],fl[i+1]+r[i]-l[i+1]);
		}
		
		else if(l[i]<=l[i+1]&&l[i+1]<=r[i]&&r[i]<=r[i+1]){
			fl[i]=min(fl[i]+l[i+1]-l[i],fr[i+1]+r[i+1]-l[i]);
			if(fr[i+1]>fl[i+1]+r[i]-l[i+1]){
				fr[i]=fl[i+1]+r[i]-l[i+1];
			}else{
				fr[i]=fr[i+1];
				r[i]=r[i+1];
			}
		}
	}
	printf("%d",min(fr[1]+as(r[1]),fl[1]+as(l[1])));
	return 0;
} 
2024/4/18 20:18
加载中...