贪心算法

2024-07-03 21:29| 来源: 网络整理| 查看: 265

排队问题1

问题描述：有n个同学在一个水龙头排队打水，每个人的打水时间是ti，请你思考，能不能找出一种排队次序，使得所有同学打完水的总时间最少

输入共两行第1行，排队人数n（n小于等于100）第2行，n个数，n个人打水时所要用的时间ti（10 ≤ ti ≤ 60），两两之间用空格隔开

输出每个人都打完水的时间总和的最小情况

样例输入

6 3 7 1 9 5 11

【样例输出】

策略分析：排队打水，水龙头只有一个，很显然打水是有一个序列依次进行下去的，当排在前面的同学打水时，排在后面的同学需要等待他打完水，才能进行下一个。很显然，需要将打水时间短的排在前面先打水，这样后面的同学等待时间才是最短的，总时间也是最短的因此 1、按照打水时间从小到大排序 2、循环进行遍历，将每一个同学的打水时间以及他的等待时间加起来 3、输出打水总时间注意：当前同学的等待时间为他前面的所有同学的打水时间总和因此可以考虑使用前缀和简单记录

代码

#include #include #define MAXN 100 + 10 int a[MAXN], b[MAXN]; //b数组记录前缀和 int main() { int n, sum = 0; scanf("%d", &n); for(int i = 1; i int n, r, sum = 0; scanf("%d %d", &n, &r); for(int i = 1; i //计算i同学的等待时间和打水时间，因为有r个水龙头因此排在他前面的那位是i-r sum += a[t]; t -= r; } } printf("%d\n", sum); return 0; }

【本文地址】

公司简介

联系我们