题解 | Bob的蛋糕店

#include<bits/stdc++.h>
using namespace std;

using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using u128=__uint128_t;
using ld=long double;

void solve()
{//考虑到n的数据量极小 进行状压枚举
//先算出最开始的质心 后续与其比较 注意到质心应是浮点数
//对于二进制的某一位 如果是一 就进行记录
//最后用记录下来的数据算出新的质心进行比较、
//注意 记录二进制0的数量时需要用n减去1的数量
//举例：001 有2个0 但是我们记录完第一个1 循环就结束了 无法获取正确的0的数量
	int n,k,sum2=0,sum1=0;
	cin >> n >> k;
	vector<int>m(n+1,0);
	for(int i=1;i<=n;i++)
	{
		cin >> m[i];
		sum1+=m[i]*i;
		sum2+=m[i];
	}
	double heart=1.0*sum1/sum2;
	for(int mask=1;mask<(1<<n);mask++)
	{
		sum1=sum2=0;
		int t=mask,cnt=1,cnt2=0;
		while(t!=0)
		{
			int temp=(t&1);
			if(temp==1)
			{
				sum1+=m[cnt]*cnt;
				sum2+=m[cnt];
				cnt2++;
			}
			cnt++;
			t>>=1;
		}
		if((n-cnt2)==k)
		{
			double a=1.0*sum1/sum2;
			if(a==heart)
			{
				cout << "Yes";
				return;
			}
		}
	}
	cout << "No";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t=1;
	//cin >> t;

	while(t--)
	{
		solve();
	}
	return 0;
}