社区讨论

好生奇怪,求助

P1016[NOIP 1999 普及组/提高组] 旅行家的预算参与者 4已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@m2474ly6
此快照首次捕获于
2024/10/11 11:56
去年
此快照最后确认于
2025/11/04 17:28
4 个月前
查看原帖
不开O2O2可以ACAC,开了O2O2TLETLE onon 2,4,52,4,5
CPP
#include<bits/stdc++.h>
using namespace std;
int n;
double c,d2,vol,res;
double dis[8],w[7];
struct node{
	int idx;
	double val;
};
deque<node> q;
bool dfs(int i){
	if(i){
		double dist=dis[i]-dis[i-1];
		while(!q.empty()){
			double temp=min(dist/d2,q.front().val);
			dist-=temp*d2,q.front().val-=temp;
			vol-=temp,res+=temp*w[q.front().idx];
			if(!q.front().val)q.pop_front();
			if(!dist)break;
		}
	}
	if(i==n+1)return true;
	if(c*d2<dis[i+1]-dis[i])return false;
	while(!q.empty()&&w[q.back().idx]>w[i])vol-=q.back().val,q.pop_back();
	q.push_back({i,c-vol}),vol+=c-vol;
	return dfs(i+1);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	double d1,p;
	cin>>d1>>c>>d2>>p>>n;
	dis[n+1]=d1,w[0]=p;
	for(int i=1;i<=n;i++)cin>>dis[i]>>w[i];
	bool flag=dfs(0);
	if(!flag)cout<<"No Solution";
	else cout<<setprecision(2)<<fixed<<res;
	return 0;
}

回复

4 条回复,欢迎继续交流。

正在加载回复...