2020-06-14 排队接水

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct A{
    int idx;
    int data;
};

A a[1000005];

void swap(int &x,int &y){
    int temp = x;
    x = y;
    y = temp;
}

int qmi(int m , int k){
  int res = 1 , t = m;
    while (k)
    {
        if (k&1)//判断是否为奇数
            res = res * t;
        t = t * t ;
        k >>= 1;
    }
    return res;
}

void quickSort(int left,int right){
    int i,j,temp;
    
    temp = a[(left+right)/2].data;//基准值
    
    i = left;
    j = right;
    
    while(i<=j){
        while (a[j].data>temp) {
            j--;
        }
        
        while (a[i].data<temp) {
            i++;
        }
        
        if (i<=j) {
            A t = a[i];
            a[i] = a[j];
            a[j] = t;
            //继续下一步
            i++;
            j--;
        }
        
    }
    
    if(left<j)quickSort(left, j);//继续分治
    if(i<right)quickSort(i, right);//继续分治
}

int read(){
    int x = 0,f = 1;
    char c = getchar();
    while (c<'0'||c>'9') {
        if (c=='-') {
            f = -1;
        }
        c = getchar();
    }
    while (c>='0'&&c<='9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x*f;
}

int main() {
    
    int n = read();
    
    for (int i = 1; i<=n; i++) {
        a[i].data = read();
        a[i].idx = i;
    }
    
    quickSort(1,n);
    
    double ans = 0;
    for (int i = 1; i<=n; i++) {
        ans += a[i].data*(n-i);
        printf("%d ",a[i].idx);
    }
    printf("\n");
    ans/=(n*1.0);
    printf("%.2lf",ans);
    
    return 0;
}