[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;
}

热门相关:总裁的秘密爱人   买妻种田:山野夫君,强势宠!   拒嫁豪门,前妻太抢手   本法官萌萌哒   今天也没变成玩偶呢