题解：CF913C Party Lemonade

题意

有

n

杯柠檬汁，每杯柠檬汁的体积为

2^{i-1}

升，价格为

c_i

卢布，问你要买

L

升，最少要花多少卢布。

思路

我们知道如果

2 \times c_i \le c_{i+1}

，我们就会买

2

瓶价格为

c_i

的柠檬汁，而不是买价格为

c_{i+1}

的柠檬汁。

我们假设购买大于等于

x

件为最优解，假设购买了

y

件也为最优解，我们从

x

与

y

的二进制位从高位往低位看，如果某一位

x

与

y

的二进制位不同，我们就从这个地方找最优解。

贴代码

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,l,len,c[35],ans,x[35];
signed main()
{
	scanf("%d%d",&n,&l);
	while(l)
	{
		x[len++]=l&1;
		l>>=1;
	}
	for(int i=0;i<n;i++)
	{
		scanf("%lld",&c[i]);
		if(i) c[i]=min(c[i],c[i-1]<<1);
	}
	for(int i=n;i<len;++i) c[i]=c[i-1]<<1;
	for(int i=0;i<max(n,len);i++)
	{
		ans=min(ans,c[i]);
		if(x[i]) ans+=c[i];
	}
	printf("%lld\n",ans);
	return 0;
}

题解：CF913C Party Lemonade

文章操作

题意

思路

相关推荐

评论

题解：CF913C Party Lemonade