山有木兮木有枝
心悦君兮君不知

标签 贪心 下的文章

你现在要洗 l 件衣服。你有 n 台洗衣机和 m 台烘干机。由于你的机器非常的小,因此你每次只能洗涤(烘干)一件衣服。

i 台洗衣机洗一件衣服需要 w_i 分钟,第 i 台烘干机烘干一件衣服需要 d_i 分钟。

请问把所有衣服洗干净并烘干,最少需要多少时间?假设衣服在机器间转移不需要时间,并且洗完的衣服可以过一会再烘干。

l \leq 10 ^ 6, n, m \leq 10 ^ 5

READ MORE

同时考虑点权和边权比较困难,如果可以把边权并到点权里,那么就可以直接贪心了。

注意到对于一条边的边权对答案的贡献

  • 如果两边都是黑点,对答案的贡献为 1 ,可以看做两个黑点分别为答案贡献了 \frac 1 2
  • 如果两边都是白点,对答案的贡献为 -1 ,可以看做两个白点分别为答案贡献了 - \frac 1 2
  • 如果一边是白点一边是黑点,贡献为 0 ,可以看做黑点为答案贡献了 \frac 1 2 的边权,白点为答案贡献了 - \frac 1 2 的贡献

这样话设置每个点的排序关键字为点权加上 \frac 1 2 的相邻边权和,按从大到小排序后奇数位为黑点,偶数位为白点即可。

READ MORE