# 【Codeforces】1216B - Shooting

### Problem Description：

Recently Vasya decided to improve his pistol shooting skills. Today his coach offered him the following exercise. He placed n cans in a row on a table. Cans are numbered from left to right from 1 to n. Vasya has to knock down each can exactly once to finish the exercise. He is allowed to choose the order in which he will knock the cans down.

Vasya knows that the durability of the i-th can is

. It means that if Vasya has already knocked x cans down and is now about to start shooting the i-th one, he will need (

⋅x+1)shots to knock it down. You can assume that if Vasya starts shooting the i-th can, he will be shooting it until he knocks it down.

Your task is to choose such an order of shooting so that the number of shots required to knock each of the n given cans down exactly once is minimum possible.

### Input Specification:

The first line of the input contains one integer n (2≤n≤1000) — the number of cans.

The second line of the input contains the sequence

,

,…,

(1≤

≤1000), where aiai is the durability of the i-th can.

### Output Specification:

In the first line print the minimum number of shots required to knock each of the n given cans down exactly once.

In the second line print the sequence consisting of n distinct integers from 1 to n — the order of indices of cans that minimizes the number of shots required. If there are several answers, you can print any of them.

3 20 10 20

43 1 3 2

4 10 10 10 10

64 2 1 4 3

6 5 4 5 4 4 5

69 6 1 3 5 2 4

2 1 4

3

2 1

### Note:

In the first example Vasya can start shooting from the first can. He knocks it down with the first shot because he haven't knocked any other cans down before. After that he has to shoot the third can. To knock it down he shoots 20⋅1+1=21 times. After that only second can remains. To knock it down Vasya shoots 10⋅2+1=21 times. So the total number of shots is 1+21+21=43.

In the second example the order of shooting does not matter because all cans have the same durability.

### AC代码：

```#include<bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for(int i = a; i <= b; i++)
#define P pair<int,int>  //first是值,second是初始下标
#define mp(x,y) make_pair(x,y)

bool cmp(P p1, P p2)
{
return p1.first > p2.first;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
vector<P> v;
int n;
cin >> n;
Up(i,1,n)
{
int _;
cin >> _;
v.push_back(mp(_,i));
}
sort(v.begin(),v.end(),cmp);
int x = 0,sum = 0,sz = v.size()-1;
Up(i,0,sz)
{
sum += v[i].first*x+1;
x++;
}
cout << sum << endl;
Up(i,0,sz)
{
cout << v[i].second << (i==sz?"\n":" ");
}
return 0;
}```

0 条评论

• ### 【PAT甲级】World Cup Betting

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### 【Codeforces】1217A - Creating a Character

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### Codeforces 706B Interesting drink

B. Interesting drink time limit per test:2 seconds memory limit per test:256 meg...

• ### 时间约束的自适应影响最大化（Social and Information Networks）

众所周知，影响最大化问题的目的是通过在扩散过程之前选择合适的种子用户来最大化一个信息级联在社交网络中的影响。在其自适应版本中，可以通过观察一定的扩散结果来选择额...

• ### UVa Automatic Editing

uva的题真的很好，每个题都能长许多知识，A了后很开心，这道题我用了两天写，只一道题就学了四个函数，成长不少 Problem E: Automatic Edit...

• ### Classifying documents with Naïve Bayes使用朴素贝叶斯分类文本

Naïve Bayes is a really interesting model. It's somewhat similar to k-NN in the ...

• ### Beini Compatible Hardware List

Beini Compatible Hardware List Do not expect that you will be able to hack WiFi ...

• ### 基于Python3 神经网络的实现

基于Python3 神经网络的实现(下载源码) 本次学习是Denny Britz（作者）的Python2神经网络项目修改为基于Python3实现的神经网络（本篇...

• ### 出现“内部错误，无法显示”

This page contains the following errors: error on line 2 at column 6: XML declar...