*******************************************************************************************************************
下课后第一件事情是干什么 ?当然是干饭啦 !
不过干饭前我们先思考一个问题——怎样才能“光速”打饭 ?
场景引入:
假设你是打饭队伍里的任意一员(1~n),对于你来说,是不是希望前面的同学打得越快越好,也就是等待时间越少越好。
那么要是每一个同学都能“得偿所愿”,是不是就能实现题目所说的最少等待时间呢。
但是偏偏就是有些慢吞吞的家伙排在你前面,这时候你又想,要是他们在我后面就好了。
哈哈,今天就浅浅施展一下魔法,满足你的两个愿望吧 !(巴啦啦能量...)
有时候局部最优是能推出全局最优的,也就是贪心。
具体实现:
首先就把慢吞吞的家伙放到后面,也就是从小到大排序。
接着计算之后每一位同学的等待时间,累加即可。//特别的,第一位同学不需要等待时间,即temptime=0;
至于temptime的计算是一个前缀和的过程,这里迭代即可,不用记录每一位,如果用for循环回溯计算,则会超时。
样例解释如下:
注意事项:
等待时间(temptime)、等待总时间(totaltime)要开long long,数据量比较大。
参考代码:
#include <iostream> #include <algorithm> using namespace std; int stutime[100005]; int main() { long long n,totaltime=0,temptime=0; cin>>n; for(int i=0;i<n;i++) { cin>>stutime[i]; } sort(stutime,stutime+n,less<int>());//时间少的先打,后面少等 for(int i=1;i<n;i++)//第一个同学不用等待,即下标为0的同学 { temptime+=stutime[i-1];//前缀和迭代 totaltime+=temptime; //等待时间累加 } cout<<totaltime; return 0; }
0.0分
2 人评分
【计算两点间的距离】 (C语言代码)浏览:1126 |
C语言程序设计教程(第三版)课后习题9.3 (C++代码)浏览:671 |
C语言程序设计教程(第三版)课后习题6.1 (C语言代码)浏览:628 |
【亲和数】 (C语言代码)浏览:859 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:614 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:661 |
sizeof的大作用 (C语言代码)浏览:1028 |
C语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:643 |
简单的a+b (C语言代码)浏览:558 |
用筛法求之N内的素数。 (C语言代码) 详解………………浏览:1017 |