求条
查看原帖
求条
747732
sunpengyu楼主2025/1/4 18:50
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int maxn=5e4+7;
int n,g,b,d,ans;
struct node{
	int x,y;
}a[maxn];
bool cmp(node a,node b){
	return a.x<a.y;
}
node minn(node a,node b){
	if(a.y<b.y) return a;
	else if(a.y>b.y) return b;
	else if(a.x<b.x) return a;
	else return b;
}
void solve(){
	int pos=0,hav=b-a[1].x,tmp=0;
	for(int i=1;i<=n;i++){
		//hav-=a[i].x-pos;
		node mn=a[i];
		for(int j=i+1;j<=n;j++){
			if(a[j].x-a[i].x>hav) break;
			mn=minn(mn,a[j]);
			if(mn.x==a[j].x&&mn.y==a[j].y) tmp=j;
		}
		hav-=mn.x-pos;
		ans+=mn.y*(g-hav);
		hav=g;
		pos=mn.x;
		i=tmp-1;
	}
	if(pos+hav<d) cout<<-1<<endl,exit(0);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>g>>b>>d;
	for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
	sort(a+1,a+1+n,cmp);
	a[n+1]={d,INT_MAX};
	if(b<a[1].x) cout<<-1<<endl,exit(0);
	for(int i=1;i<n;i++){
		if(g<a[i+1].x-a[i].x){
			cout<<-1<<endl;
			exit(0); 
		}
	}
	//if(g<d-a[n].x) cout<<-1<<endl,exit(0);
	solve();
	cout<<ans;
	return 0;
}

此代码总是输出-1,思路就是贪心不断向终点靠近

2025/1/4 18:50
加载中...