题解 P1223 【排队接水】

f112358 · 2017-05-06 21:31:13 · 题解

有一个巧妙的存数据方式来输出排序之后编号的顺序

（针对快排懒得用结构体的同学）

因为n<=1000

所以给每个ti都*1001，在加上当前序号

可以保证排序的时候序号不干扰排序

又可以方便输出序号（只需mod1001输出序号，／1001 输出时间）

具体代码如下

//
//  main.cpp
//  Water containing
//
//  Created by Leonardo Cullen on 2017/5/6.
//  Copyright © 2017年 Leonardo Cullen. All rights reserved.
//
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
double sum;
long int n;
long long int t[1001];
double ans;
int main(int argc, const char * argv[])
{
    cin>>n;
    int x;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        t[i]=x*1001+i;
    }
    sort(t+1,t+1+n);
    for(int j=1;j<=n;j++)
    {
        cout<<t[j]%1001<<" ";
        sum+=t[j]/1001*(n-j);
    }
    cout<<endl;
    ans=sum/n;
    printf("%0.2lf",ans);
    return 0;
}