首页 > Hacker, pack your bags!
开通博客写题解
头像 WuliWuliiii
发表于 2020-12-23 10:28:59
题意：有N条线段，每天线段有左右端点l、r，并且线段的长度是r-l+1，且线段有价值c，现在我们想要找两条线段，使得两条线段的长度和为X，并且两线段不相交。如果没有这样的答案输出-1，否则输出最小价值。那么，很简单的，我们可以对l进行生序排序，于是直接查r在“l”之前的线段，我们用map去记录一下对 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 MYCui_
发表于 2020-12-21 22:24:17
前言 这是一道很棒的思维题/数据结构！ 难度：2星做法：二分，排序 线段树 题意： 给定 以及 个区间，区间 有左端点 和 右端点 以及 花费 ,要求你选出两个区间,满足下面两个条件: 两个区间没有交集 两个区间的长度和等于 (这里的长度为 ) 现在要求你选出的这两个区间的权值 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 issue是云哥的小迷×呀
发表于 2020-12-25 20:24:18
传送门 对区间按照左端点进行排序 那么对于每条线段的右端点 因为左端点是递增的m往右二分出一个区间的线段都是不相交的 但是还需要找到固定长度的 做法 枚举每个线段,把这条线段当作右端的线段,去左端的线段里找最小值 维护两个线段数组和 按照区间左端点小到大排序,按照右端点小到大排序 现在考虑线段和哪 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 熠丶
发表于 2020-12-23 15:23:37
做法： 根据区间长度存线段，然后把每种长度的线段根据左端点进行排序 枚举第二个区间的长度的所有线段，用minu存当前最优的第一个线段 按照上述模拟即可 代码 #include <bits/stdc++.h> using namespace std; #define pb push_b 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”