社区讨论
好生奇怪,求助
P1016[NOIP 1999 普及组/提高组] 旅行家的预算参与者 4已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @m2474ly6
- 此快照首次捕获于
- 2024/10/11 11:56 去年
- 此快照最后确认于
- 2025/11/04 17:28 4 个月前
不开可以,开了会
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 条回复,欢迎继续交流。
正在加载回复...