首页 > Groundhog Looking Dowdy
开通博客写题解
头像 mutou01
发表于 2020-08-08 20:10:43
2020暑期多校D9-F 思路+证明主为自用，欢迎指正。 https://ac.nowcoder.com/acm/contest/5674/F 前置知识：尺取法：一种反复推进区间的头尾，求出满足条件的最小区间的技巧。 题意：从n天中选m天，要让m天所穿的衣服价值的最大值与最小值差值最小。 思路：由于 展开全文
去ta的博客 赞 (5) 回复(1) 收起
头像 TitanZhang
发表于 2020-08-08 20:20:26
题目大意 有n天，每天穿一件衣服，第天有件衣服可以穿，穿第件衣服的的权值为。求其中任意m天中，所穿衣服的权值最大值与最小值的最小差。 解题思路 我们要做的是最小化最大最小值之差，所以必要的肯定是把所有衣服按照权值从小到大排个序。我们可以把每件衣服打一个标记，记录一下是从哪一天来的。然后在里面维护一个 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 梁好问tanget90°
发表于 2020-08-08 19:51:32
原题链接：https://ac.nowcoder.com/acm/contest/5674/F 题目描述 土拨鼠（Groundhog）发现苹果（Apple）比以前对他更不亲近了。同时他发现他的打扮过时了。但土拨鼠过于懒惰，他只列出了接下来n天能穿的衣服。在第i天，他的第j件衣服的权值为 。在这n 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”