求本题贪心做法 hack

枚举参加的比赛场次数，每次从剩余的 perf 中选取最靠前的最大值，并选择，并计算对应 rating。

感觉在

-\frac{1200}{\sqrt{k}}

确定时，只需要最大化前面的式子即可。但为什么 WA 呢？

或者给出反例也可。

代码：

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long double var;

int n;
int s[5005];

var perf[5005];

var k;
var sumk;

var rating;

var marating=-114514;

int main(){
	ios::sync_with_stdio(0);
	
	cin>>n;
	for(int i=1;i<=n;++i) cin>>s[i];
	
	for(int i=1;i<=n;++i){
		int maxp=0,maxj;
		for(int j=1;j<=n;++j){
			if(s[j]>maxp) maxp=s[j],maxj=j;
		}
		perf[maxj]=s[maxj],s[maxj]=0;
		
		k=1,rating=0,sumk=0;
		
		for(int j=n;j>=1;--j){
			if(perf[j]){
				rating+=perf[j]*k,sumk+=k;
				k*=0.9;
			}
		}
		
		rating=rating/sumk-1200./sqrtl(i);
		
		marating=max(rating,marating);
	}
	
	cout<<fixed<<setprecision(16)<<marating<<endl;
	
	return 0;
}

求本题贪心做法 hack

讨论操作

回复

相关推荐

求本题贪心做法 hack