网站开发制作计算器,怎样去掉2345网址导航,海外网站,ppt免费下载完整版免费下载题意#xff1a;有 1∼n1 \sim n1∼n nnn 个城市排成一行#xff0c;给定每个城市的单位距离油价和两个城市间的距离、油箱容量#xff0c;求 111 到 nnn 最小代价。
用 multiset 来维护当前油箱中的油的价格。
在每个城市假装把油加满。如果发现这个城市的油比油箱里的一…题意有 1∼n1 \sim n1∼n nnn 个城市排成一行给定每个城市的单位距离油价和两个城市间的距离、油箱容量求 111 到 nnn 最小代价。
用 multiset 来维护当前油箱中的油的价格。
在每个城市假装把油加满。如果发现这个城市的油比油箱里的一些便宜就把这些油都退掉。
跑的时候用油箱里最便宜的油。到达终点后如果有多余的油就全部退掉。
合法性退掉的油是从买的时候到现在为止没有用过的退掉相当于没有买。
最优性因为每次油都加满了如果不优会被退掉感性理解是最优的。
复杂度 O(nlogn)O(n\log n)O(nlogn)
#include iostream
#include cstdio
#include cstring
#include cctype
#include set
#include utility
#define MAXN 100005
using namespace std;
typedef long long ll;
inline int read()
{int ans0;char cgetchar();while (!isdigit(c)) cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return ans;
}
int d[MAXN],c[MAXN];
typedef pairint,int pi;
multisetpi s;
int main()
{freopen(drive.in,r,stdin);freopen(drive.out,w,stdout);int n,m;nread(),mread();for (int i1;in;i) d[i]read();d[n2]d[n1]d[n];for (int i1;in;i) c[i]read();int resm;ll ans0;for (int i1;in1;i){while (!s.empty()s.rbegin()-firstc[i]) ress.rbegin()-second,ans-(ll)s.rbegin()-first*s.rbegin()-second,s.erase(--s.end());s.insert(make_pair(c[i],res)),ans(ll)c[i]*res,res0;int tresd[i1]-d[i];if (tm) return puts(-1),0;while (!s.empty()ts.begin()-second) t-s.begin()-second,s.erase(s.begin());if (!s.empty()){pi tmp*s.begin();s.erase(s.begin());tmp.second-t;s.insert(tmp);}}coutans;return 0;
}
