2020-2021:teams:too_low:cfedu92hj
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:too_low:cfedu92hj [2020/07/31 17:25] jim [C.Good String] |
2020-2021:teams:too_low:cfedu92hj [2020/07/31 17:37] (当前版本) jim [E.Segment Intersections] |
||
|---|---|---|---|
| 行 138: | 行 138: | ||
| ===== D.Segment Intersections ===== | ===== D.Segment Intersections ===== | ||
| - | ** [[https://codeforces.com/contest/1389/problem/A]] | ||
| - | ** 题意：找到[l, r]范围内的两个数x, y使得其最小公倍数也在[l, r]范围内。 | + | 题意：给定2种区间，每种区间有n个，2种不同区间为一组。每次操作可以将区间向左/右扩展一个单位。求使各组区间重叠长度达到k的最小步数。 |
| + | 最优情况下，扩展时有3个过程：不相邻->相邻->区间完全重叠->继续扩展 | ||
| + | |||
| + | 三个过程的重叠数收入分别为0，扩展数、扩展数/2 | ||
| + | |||
| + | 记录每个过程的扩展长度，枚举选i组区间扩展到重叠k次需要的扩展数，取最小值。 | ||
| + | | ||
| + | 需要注意已经重叠的情况 | ||
| <hidden> | <hidden> | ||
| <code cpp> | <code cpp> | ||
| + | #include <bits/stdc++.h> | ||
| + | |||
| + | using namespace std; | ||
| + | typedef long long LL; | ||
| + | |||
| + | int main() { | ||
| + | int t = 0; | ||
| + | cin >> t; | ||
| + | while (t--) { | ||
| + | LL n, k; | ||
| + | cin>>n>>k; | ||
| + | int l1, r1, l2, r2; | ||
| + | cin>>l1>>r1>>l2>>r2; | ||
| + | LL pre = max(0, max(l1, l2) - min(r1, r2)); | ||
| + | LL most = max(r1, r2) - min(l1, l2); | ||
| + | LL ist = max(0, min(r1, r2) - max(l1, l2) )* (LL)n ; | ||
| + | k -= ist; | ||
| + | if(k <= 0){ | ||
| + | cout<<0<<endl; | ||
| + | continue; | ||
| + | } | ||
| + | LL ans = INT32_MAX; | ||
| + | for (int i = 1; i <= n; ++i) { | ||
| + | LL cur = pre * i; | ||
| + | cur += min((LL)k, most * i); | ||
| + | if(k > most * i){ | ||
| + | cur += 2 * (k - most * i); | ||
| + | } | ||
| + | ans = min(ans, cur); | ||
| + | } | ||
| + | cout<<ans<<endl; | ||
| + | } | ||
| + | |||
| + | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
| - | ===== E.Segment Intersections ===== | + | |
2020-2021/teams/too_low/cfedu92hj.1596187559.txt.gz · 最后更改: 2020/07/31 17:25 由 jim
