排队打水问题 （C++)

一道典型的贪心算法问题

很多解释都是把打水和等待分开，可以不分开，按列来算，找到后面人和第一个使用水龙头时间的关系即可。最终所有的t[i]相加就行。

int main()
{int n,r;//n 人 r 水龙头 cin>>n>>r;const int a=n;//这样就可以自定义数组大小int t[a],sum;for(int i=0;i<n;i++) {cin>>t[i];}sort(t,t+n);for(int i=r;i<n;i++)//从r开始，需要算上一个人的接水时间 {t[i]+=t[i % r+(i/r-1)*r]; // 所有>=第二轮的人，都适用 }for(int i=0;i<n;i++){sum+=t[i];}cout<<sum<<endl;}

sort完之后，
第一轮打水的时间不用管，因为只有自己的时间。
第n轮的人所用时间为：自己打水的时间和上一个人所用时间之和，
例如：t[r]=t[0]+t[r]; (第二排）

第n轮的时间，都和第一轮找关系:
*t[i%r+(i/r-1)r],
这里一定不要分解因式了！！！！
因为“ / ”是整除，分解之后答案就不对啦！

i%r：第i%r个水龙头第一个人使用的时间
(i/r-1) * r :（轮数-1）*r

举个例子：
A B C (ABC三个水龙头）
0 1 2 (第一轮）（0号 1 号 2号接水人）
3 4 5 (第二轮）
6 7 8 (第三轮）
9 …

那么:

t[4]=t[1]+t[4]	//t[4] 4=1加上1个3   
t[7]=t[4]+t[7]  //t[7] 7=1加上2个3
这里的1就是余数，表明是1号对应的水龙头 几个就是（轮数-1）【找规律得】

所以就有了针对于从第二轮开始的打水人的公式：

t[i]+=t[i % r+(i/r-1)*r]; // 所有>=第二轮的人，都适用 

-end-

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！