求助这题为什么贪心不行
查看原帖
求助这题为什么贪心不行
274209
AzzyZhe楼主2021/2/9 19:46

rt,仔细想想 确实还是不大明白

个人思路预处理出和哥哥直接比拼的选手,尽可能保留每场粉丝最多但能被哥哥击败的选手,结果只有20pts,都是少部分WA

不知是思路还是代码问题,求助

20pts代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#define MAXN (1<<18)
using namespace std;
typedef long long int64;
typedef unsigned long long uint64;
//#define int uint64
int k,m,n,lim;
int a[MAXN];//ty
inline int xwin(int a,int b)
{
	if(a>b){
		if(a<=lim)
			return a;
		if(a-b<=m)
			return b;
		return a;
	}else{
		if(b<=lim)
			return b;
		if(b-a<=m)
			return a;
		return b;
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	int p;
	while(T--)
	{
		cin>>k>>m;
		n=1<<k;
		for(int i=0;i<n;i++)
			cin>>a[i];
		lim=a[0]+m;
		for(int i=1;i<k;i++)
			for(int t=1<<i,j=t,tt=t>>1;j<n;j+=t)
				//cout<<j<<','<<j+tt<<' '<<a[j]<<' '<<a[j+tt]<<endl,
				a[j]=xwin(a[j],a[j+tt]);
		p=1;
		while(p<n)
		{
			//cout<<a[p]<<'#';
			if(lim<a[p])
				goto GG;
			p<<=1;
		}
		cout<<"Kotori\n";
		continue;
	GG:;
		cout<<"Yoshino\n";
	}
	return 0;
}
2021/2/9 19:46
加载中...