全WA求助啊(心态已炸)
查看原帖
全WA求助啊(心态已炸)
506081
BlueSky_楼主2021/7/3 15:03
#include<bits/stdc++.h>
#define MAX 999999999999999999
using namespace std;

struct node{
	long long c,x;
};

bool cmp(node a,node b){
	return a.x<b.x;
}

long long n,s,t,S,T,f1[101000],f2[101000],ans=MAX,cnt,dp[101000];
node a[101000];

void dfs(int x,int pre){
	if(pre>=dp[x]) return;
	dp[x]=pre;
	if(f1[x]!=0) dfs(f1[x],pre+(a[x].x-a[f1[x]].x)*a[x].c);
	if(a[f2[x]].x>=t) ans=min(ans,pre+(t-a[x].x)*a[x].c);
	else dfs(f2[x],pre+(a[f2[x]].x-a[x].x)*a[x].c);
}

int main(){
	cin>>n>>s>>t;
	for(int i=1;i<=n;i++){
		cin>>a[i].c>>a[i].x;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
		if(a[i].x==s) S=i;
	}
	for(int i=1;i<=n;i++){
		cnt=i-1;
		while(a[cnt].c>=a[i].c&&cnt>=1) cnt--;
		f1[i]=cnt;
	}
	for(int i=n;i>=1;i--){
		cnt=i+1;
		while(a[cnt].c>=a[i].c&&cnt<=n) cnt++;
		f2[i]=cnt;
	}
	a[n+1].x=MAX;
	for(int i=1;i<=n;i++) dp[i]=MAX;
	dfs(S,0);
	cout<<ans;
	return 0;
}
2021/7/3 15:03
加载中...