正向推导出贪心推公式排序的结论

¶方法总结

(1)假设结论为按照规则$f$排序，其相反结论为$!f$；
(2)假设先按照$!f$排序，再按照$f$对序列元素$a_i,a_{i+1}$进行调整，得到关系$g(a_i,a_{i+1})$；
(3)再由$g$化简推导出$!f$，其相反结论即为$f$。

¶例题1 国王游戏

¶分析

设大臣$i$左右手数字分别为$l_i,r_i$,

假设按照$!f$排序，

第$i$个大臣和第$i+1$个大臣的奖赏为$\frac{l_1l_2…l_{i-1}}{r_i}$,$\frac{l_1l_2……l_{i}}{r_{i+1}}$,

按照$f$调整后得到$\frac{l_1l_2……l_{i-1}}{r_{i+1}}$,$\frac{l_1l_2……l_{i-1}l_{i+1}}{r_i}$,

因为$f$为正确结论，则必有调整后的最大值小于调整前的最大值，

即关系$g:max(\frac{l_1l_2……l_{i-1}}{r_i},\frac{l_1l_2……l_i}{r_{i+1}})>max(\frac{l_1l_2……l_{i-1}}{r_{i+1}},\frac{l_1l_2……l_{i-1}l_{i+1}}{r_i})$,

化简得$g:max(r_{i+1},l_rr_r)>max(r_i,l_{i+1}r_{i+1})$,

可以推导出$l_ir_i>l_{i+1}r_{i+1}$,即为$!f$,

其相反结论$f:l_ir_i<l_{i+1}r_{i+1}$。

所以本题方法为按照$l_ir_i$从小到大排序。

¶python代码

1
2
3
4
5
6
7
8
9
10
11
12

n=int(input())
w=[]
for i in range(n+1):
    a,b=map(int,input().split())
    w.append((a,b))
w=[w[0]]+list(sorted(w[1:],key=lambda x:(x[0]*x[1])))
res=0
s=w[0][0]
for i in range(1,n+1):
    res=max(res,s//w[i][1])
    s*=w[i][0]
print(res)

¶例题2 耍杂技的牛

设奶牛$i$体重和强壮程度分别为$w_i,s_i$,

假设按照$!f$排序，

第$i$个奶牛和第$i+1$个奶牛的风险值为$w_1+w_2…+w_{i-1}-s_i$,$w_1+w_2…+w_i-s_{i+1}$,

按照$f$调整后得到$w_1+w_2…+w_{i-1}-s_{i+1}$,$w_1+w_2…+w_{i-1}+w_{i+1}-s_i$,

因为$f$为正确结论，则必有调整后的最大值小于调整前的最大值，

即关系$g:max(w_1+w_2…+w_{i-1}-s_i,w_1+w_2…+w_i-s_{i+1})>max(w_1+w_2…+w_{i-1}-s_{i+1},w_1+w_2…+w_{i-1}+w_{i+1}-s_i)$,

化简得$g:max(s_{i+1},w_i+s_i)>max(s_i,w_{i+1}+s_{i+1})$,

可以推导出$w_i+s_i>w_{i+1}+s_{i+1}$,即为$!f$,

其相反结论$f:w_i+s_i<w_{i+1}+s_{i+1}$。

所以本题方法为按照$w_i+s_i$从小到大排序。

¶python代码

1
2
3
4
5
6
7
8
9
10
11
12

n=int(input())
cow=[]
for i in range(n):
    w,s=map(int,input().split())
    cow.append((w,s))
cow.sort(key=lambda x:(x[0]+x[1]))
suma=0
res=-float('inf')
for i in range(n):
    res=max(res,suma-cow[i][1])
    suma+=cow[i][0]
print(res)