[ABC318C] Blue Spring 题解
[ABC318C] Blue Spring 题解
题意简述
主人公出去旅游要买票，共有若干天，每天要花不同钱。现在有“通行证”出售，通过购买通行证，可以在某一天直接用通行证，以此来省去当天原本需要花费的票价。通行证只能一套一套买，每套中有 \(D\) 个，买一套要花费 \(P\) 元。可以购买任意套数的通行证，求怎样最省钱。
解题思路
首先发现天和天之间独立，可以排序，排序不影响买票总价的性质。于是我们将原序列从小到大排序，方便处理。
我们将一套通行证中，每张通行证的平均单价计算出来，即 \(\frac{P}{D}\)（注意可能不是整数），然后我们发现，假如说一套中只有一张通行证，那么显然，只要某天票价高于通行证，就购买通行证。
假如有一套中有多于一张通行证，我们考虑贪心地按每天花费大到小，进行比较来购买通行证。如果当前买通行证单价比要替换掉的天数的花费全都低，那么显然是优的。而如果买的太多了，当前买通行证单价比要替换掉的天数的花费全都高，那么还不如不买这个通行证。
综上，我们统计出所有花费高于通行证单价的日期数量 \(m\)，只需要计算购买 \(\lfloor \frac{m}{D} \rfloor\) 套通行证和购买 \(\lceil \frac{m}{D} \rceil\) 套通行证后，总花费的最小情况就行。为什么不多买或者少买在上一段说过了。
代码
注意特判如果 \(\lceil \frac{m}{D} \rceil\) 超过了 \(n\)（总天数）的情况。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 5;
LL n,d,p;
LL a[N],s[N];
double b[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> d >> p;
for(int i = 1;i <= n;i++)
{
cin >> a[i];
}
sort(a+1,a+1+n);
for(int i = 1;i <= n;i++)
{
s[i] = s[i-1] + a[i];
b[i] = a[i];
}
LL idx = lower_bound(b+1,b+1+n,(double)p/(double)d) - b;
LL tmp = (n - idx + 1)/d;
LL ans = s[n-tmp*d+1-1] + tmp*p;
if(n-(tmp+1)*d+1-1 < 1)
ans = min(ans,(tmp+1)*p);
else
ans = min(ans,s[n-(tmp+1)*d+1-1]+(tmp+1)*p);
cout << ans << "\n";
return 0;
}