P9833 44pts求调
  • 板块灌水区
  • 楼主a_little_carrot
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/5/3 12:09
  • 上次更新2024/5/3 15:19:48
查看原帖
P9833 44pts求调
1042960
a_little_carrot楼主2024/5/3 12:09
// 未特别说明距离都指离目的地的距离
#include<bits/stdc++.h>
using namespace std ;
struct NODE{
	long long dis,oil ;
	friend bool operator <(NODE a,NODE b) {
		return a.dis<b.dis ;
	}// 重载 大顶小根
} ;
bool cmp(NODE a,NODE b){return a.dis>b.dis;}
long long n,l,p,ans ;
NODE s[10004] ;
priority_queue<NODE> que ;
int main() {
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) ;
	cin>>n ;
	for(int i=n;i>0;--i)cin>>s[i].dis>>s[i].oil ;
	sort(s+1,s+n+1,cmp) ;
	cin>>l>>p ;// 距离 当前油量
	if(s[1].dis-l>p){cout<<-1;return 0;}
	que.push(s[1]);long long u=1;p-=l-s[u].dis;l=s[u].dis ;
	// que先搞进去一项进入循环 u 指针 s 加油站距离和油量 
	while(l!=0) {
		++u ;
		if(l-s[u].dis<=p) {// 可以跑就加上
			que.push(s[u]) ;
			p-=l-s[u].dis;l=s[u].dis ;
		}else {
			while(p<l-s[u].dis) {// 一直加到可以跑
				NODE t=que.top();que.pop() ;
				p+=t.oil;ans++ ;
				if(que.empty()&&p<l-s[u].dis) {
					cout<<-1 ;
					return 0 ;
				}
			}--u ;// 多加了 重新算
		}
	}
	cout<<ans ;
	return 0 ;
}
2024/5/3 12:09
加载中...