M21554: 排队做实验

greedy, http://cs101.openjudge.cn/practice/21554

某学院的学生都需要在某月的1号到2号期间完成课程实验，他们每个人的实验需要持续不同的时长。而实验室管理员要安排这些学生，按照一定顺序，在1号到2号期间全部完成实验。假设该学院的实验室同时只能容纳一名学生实验，而这些学生都非常积极，都希望被排在1号的第一个尽快完成实验。

假设该学院有n个学生，实验室管理员收到了n个学生每位需要占用实验室的时长T1,T2,...,Tn，由于学生发送预约邮件的时间比较接近，没办法完全按照先到先得的办法给学生分配实验时间（实验时间相同的话，先到先得）。管理员很犯愁，他希望有一种能让所有学生平均等待时间尽可能小的顺序，来安排这n位同学的实验时间，请问你能帮帮他吗？

输入

输入为2行第一行为n，为学生人数(n<=1000) 第二行分别表示第一位学生到第n位学生的实验时长T1，T2，…，Tn，每个数据间有一个空格

输出

输出为2行第一行为一种学生实验顺序，即1到n的一种排列第二行为这种方案下的平均等待时间（精确到小数点后两位）

样例输入

Sample1 Input:
10
81 365 72 99 22 7 444 203 1024 203

Sample1 Output:
6 5 3 1 4 8 10 2 7 9
431.90

样例输出

Sample2 Input:
18
490 329 970 969 435 981 839 177 616 857 583 551 443 565 393 237 804 398 

Sample2 Output:
8 16 2 15 18 5 13 1 12 14 11 9 17 7 10 4 3 6
3750.89

提示

等待时间的定义是从时刻0开始的。第i个学生要等待前面i-1个学生都做完实验。

来源：cs101 2020 Final Exam

python

n = int(input())
# 读取输入并直接创建排序后的列表
t = sorted(enumerate(input().split(), 1), key=lambda x: int(x[1]))

# 提取索引，即为答案
ans = [i[0] for i in t]
print(*ans)

# 计算动态规划数组dp，并计算平均值
dp, total = [0], 0
for _, value in t[:-1]:
    total += int(value)
    dp.append(total)

# 计算平均值时去掉dp的第一个元素（它是0），然后除以n得到平均数
average = (sum(dp) - dp[0]) / n
print(f'{average:.2f}')

思路：时间短的先做时间长的后做，然后累加求总时间就行了。

python

n = int(input())
t = [(i, int(j)) for i, j in enumerate(input().split(), 1)]
tt = t.copy()
tt.sort(key = lambda x: x[1])

ans = []
for i in tt:
    ans.append(i[0])

print(*ans)     

dp = [0]*n
dp[0] = 0
for i in range(1, n):
    dp[i] = dp[i-1] + tt[i-1][1]
    
print('{:.2f}'.format(sum(dp)/n))

python

n = int(input())
time = list(map(int, input().split()))
students = sorted([(time[i], i + 1) for i in range(n)])
print(" ".join(map(lambda stu: str(stu[1]), students)))
pre_sum, total = 0, 0
for stu in students:
    total += pre_sum
    pre_sum += stu[0]
print(f"{total/n:.2f}")

2021fall-cs101，陈锦洋。

第三行的sorted 的使用我觉得比较精妙。贪心的思路主要体现在让用时短的人先做实验。

python

n = int(input())
*L, = map(int,input().split())
od = sorted(range(1, n+1), key = lambda x: L[x - 1])
L.sort()
t = sum((n-i-1) * L[i] for i in range(n)) / n

print(*od)
print('{:.2f}'.format(t))

2021fall-cs101，梁天书。

enumerate 和zip 函数两种方法确实也比较简单，但是由于之前对这两个函数印象不是特别深，因此自己利用基本函数写了很长一段。

python

n=int(input());i=0
time=list(map(int, input().split()))
tim=time[0:];pos=[];t=0
tim.sort()
while i < len(tim):
    if tim.count(tim[i])<2:
        a=time.index(tim[i])
        pos.append(a+1)
        t+=(n-i-1)*tim[i]
        i+=1
    else:
        b=tim.count(tim[i])
        c=-1;j=0
        while j<b:
           a=time.index(tim[i],c+1)
           pos.append(a+1)
           c=a
           t+=(n-i-j-1)*tim[i]
           j+=1
        i+=b
m=t/n
print(' '.join(str(x) for x in pos))
print(format(m,'.2f'))

M21554: 排队做实验 ​

M21554: 排队做实验