向上取整方法:
1,转化:向上取整转化为向下取整
2,ceil函数
ceil(dist * 1.0 / d)
通过将dist乘以1.0,将其转换为浮点数。这样,在计算dist * 1.0 / d时,除法运算将得到一个准确的浮点数结果,而不会截断小数部分。
例如,如果dist是整数类型且等于5,d是整数类型且等于2,那么在计算dist / d时,结果将是2而不是2.5。但是,如果将dist乘以1.0变为浮点数,就可以得到准确的结果2.5,从而在后续的运算中产生正确的结果。
倒着求证
到i站点,需要多少油,到i-1站点需要多少油,这两个一减,就是i-1到i这段距离需要的油
补油的话,是从经过的最便宜的站点加油,才价格最低
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, d;
int v[N], a[N];
int main()
{
scanf("%d%d", &n, &d);
for (int i = 1; i < n; i ++ ) scanf("%d", &v[i]);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
LL res = 0, oil = 0, dist = 0;
int price = a[1];
for(int i=2; i<=n; i++)
{
dist += v[i - 1]; //i - 1站点到i站点,
LL t = (dist + d - 1 ) / d - oil; //i-1到i还需多少油
res += t * price; //还需多少油*价格
oil += t; //加上还需要的油
price = min(price, a[i]); //补油按便宜的来
}
cout << res << endl;
return 0;
}
正着求
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, d;
LL v[N], a[N], y[N];
int main()
{
scanf("%d%d", &n, &d);
for(int i=2; i<=n; i++) cin >> v[i];
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for(int i=2; i<=n; i++)
{
v[i] += v[i - 1]; //站点到出发点的距离
y[i] = ceil(v[i] * 1.0 / d); //计算起点到当前站点所需要的油
}
LL res = 0;
LL price = a[1];
for(int i=2; i<=n; i++)
{
res += (y[i] - y[i - 1]) * price;
price = min(price, a[i]);
}
cout << res << endl;
return 0;
}