[SGU 165 Basketball]贪心、排序

【题目大意】

一列篮球队员身高从1950mm至2050mm不等，而他们的平均身高却正好是2000mm。要求找到这些队员的一个排列，满足对任意K任意连续K个球员，他们的总身高和2000*K mm相差不超过10cm：即100mm。

【算法分析】

排序，然后如果前缀和<0，那么加大的，否则加小的。

注意本题没有无解情况。

因为给定了平均身高和队员身高范围，所以必然可以维护前缀和∈[-50,+50]

所以SUM(S[I]-S[J])∈[-100,100]。

【其它】WA了几次，因为忘记对A数组加个标号了。。。而样例又是排好序的，所以就以为没错。

998260 10.02.10 17:56 edward 165 .CPP Accepted 71 ms 103 kb

【CODE】

#include #include #include #include #include using namespace std;
#define N 6111
struct data{double a;int diff;}a[N];
int n,ans[N];

void init(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        double tt;
        scanf("%lf",&tt);
        a[i].a=tt*1000;
        a[i].a-=2000;
        a[i].diff=i;
    }
}

inline double fabs(double x){
    if (x<0) return -x;
    return x;
}   

void work(){
    int i=1,j=n;
    double sum=0;
    for (int k=1;k<=n;k++){
      if (sum<0){
          sum+=a[j].a;
          ans[k]=a[j].diff;
          j–;
      }   
      else{
          sum+=a[i].a;
          ans[k]=a[i].diff;
          i++;
      }   
    }   
    printf("yesn");
    for (i=1;i<=n;i++){
        printf("%d",ans[i]);
        if (i!=n) printf(" ");
    }   
    printf("n");
}   

bool cmp(data x, data y){
    return x.a}   

int main(){
    init();
    sort(&a[1],&a[n+1],cmp);
    work();
}