题目名称 | 2035. [BOI]名次排序 |
---|---|
输入输出 | sorting.in/out |
难度等级 | ★★★ |
时间限制 | 1000 ms (1 s) |
内存限制 | 256 MiB |
测试数据 | 11 |
题目来源 | mikumikumi 于2015-09-11加入 |
开放分组 | 全部用户 |
提交状态 | |
分类标签 | |
分享题解 |
通过:2, 提交:2, 通过率:100% | ||||
mikumikumi | 100 | 0.059 s | 4.92 MiB | C++ |
ceerRep | 100 | 0.068 s | 3.69 MiB | C++ |
关于 名次排序 的近10条评论(全部评论) | ||||
---|---|---|---|---|
由于懒得写SPJ了,所以可能会比较坑;
但只要按照最优策略(即优先将小的数向后移动),应该是可以过的。 总而言之,慎做 |
已知参赛选手的得分,你的任务是按照得分从高到底给出选手的排名。
遗憾的是,保存选手信息的数据结构只支持一种操作,即将一个选手从位置i移动到位置j,该移动不改变其他选手的相对位置,即如果i > j,位置j和位置i-1之间的选手的位置都比原来加1,相反如果 i < j,则位置i+1和位置j之间的选手的位置都比原来减一。上述移动的操作的代价定义为i+j,这里,位置编号从1开始。请你编程确定一个移动选手的步骤,将选手按照得分从高到低排序,并使整个移动过程的总代价最小。
第一行为一个整数n(2<=n<=1000),表示选手的人数;接下来的n行,每行一个非负整数Si( 0<=Si<=1000000),表示一个选手的得分。你可以认为每人的得分是不同的。
文件sorting.out的第一行为一个整数,表示移动的次数,接下来的每一行表示一个移动步骤,每个移动步骤用两个整数i, j表示,表示位置i的选手移动到位置j,i和j之间有一个空格隔开。(优先移动i>j的情况)
5 20 30 5 15 10
2 3 5 2 1