SGU 165.Basketball

时间:2022-01-28 05:04:28

题意
       输入n个在[1.95,2.05]范围内的数。
       保证他们的平均数为2.00。
       现在要求把这些数调整出一个顺序,
       使得任意长度为K的子段和与2.00*K的差值的绝对值不超过0.01(K=1,2...,n)


Solution:

由于数的范围,和平均数为2,保证了有解。

对所有数-2,使得前缀和的绝对值不超过0.1即可。

由于数的范围在1.95~2.05之间,减去2后小于0的数一定等于大于0的数。

只要每两个位置放上一正一负即可

code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
int n,m;
double s[6009];
int ans[6009],g[6009];
bool cmp(int a,int b){
return s[a]<s[b];
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>s[i],s[i]-=2,g[i]=i;
sort(g+1,g+1+n,cmp);
int i=1,j=n,t=0;
double tem=0;
while(t<n){
if(tem>=0){
tem+=s[g[i]];
ans[++t]=g[i++];
}
else{
tem+=s[g[j]];
ans[++t]=g[j--];
}
}
puts("yes");
for(int i=1;i<=n;i++)
cout<<ans[i]<<" ";
return 0;
}