首页 › 题库 › C/C++编程考级 › C/C++编程四级 › 简答题
简答题 偏难
#13173

排队序列 已知现在有 n 个人需要打电话,他们已经排好了队伍,每个人打电话的时间为T i 。请你帮助他们找到一个排队打电话的队列方案,使队伍的平均等待时间更短。…

排队序列

已知现在有 n 个人需要打电话,他们已经排好了队伍,每个人打电话的时间为Ti。请你帮助他们找到一个排队打电话的队列方案,使队伍的平均等待时间更短。

输入格式

第一行:一个正整数n,表示一共n个人。

第二行:n个数字,分别表示第1个人到第n个人每人的打电话时间T1,T2,…,Tn,每个数据之间有1个空格。

输出格式

第一行为一种排队顺序,即原先队列编号1到n的一种排列;

第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位,按照C语言的浮点数保留规则进行保留)。


输入样例

10 
56 12 1 99 1000 234 33 55 99 812

输出样例

3 2 7 8 1 4 9 6 10 5
291.90

说明提示

1≤n≤100000

1≤Ti≤1000000

如果有多种排列都可以让平均等待时间最短,则输出其中字典序最小的序列。字典序指的是英文单词在字典中排序使用的规则顺序。

限制

时间限制:1000ms

内存限制:512MiB

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; #include &lt;iomanip&gt; using namespace std; struct Person {     int id;     int time; }; bool cmp(const Person &amp;a, const Person &amp;b) {     if(a.time != b.time) return a.time &lt; b.time;     return a.id &lt; b.id; } int main() {     int n;     cin &gt;&gt; n;     vector&lt;Person&gt; people(n);          for(int i = 0; i &lt; n; i++) {         cin &gt;&gt; people[i].time;         people[i].id = i + 1;     }          sort(people.begin(), people.end(), cmp);          long long total_wait = 0;     long long current_wait = 0;          for(int i = 0; i &lt; n; i++) {         if(i &gt; 0) cout &lt;&lt; " ";         cout &lt;&lt; people[i].id;         if(i &gt; 0) current_wait += people[i-1].time;         total_wait += current_wait;     }          cout &lt;&lt; endl;     double avg_wait = (double)total_wait / n;     cout &lt;&lt; fixed &lt;&lt; setprecision(2) &lt;&lt; avg_wait &lt;&lt; endl;          return 0; }</pre>
这道题暂未补解析。