首页 > 代码库 > SGU 165.Basketball

SGU 165.Basketball

2024-07-17 09:30:23   218人阅读

题意
       输入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;}

 

　　

 


联系
我们