CF1389D-Segment Intersections

题目:

题目描述:

You are given two lists of segments $ [al_1, ar_1], [al_2, ar_2], \dots, [al_n, ar_n] $ and $ [bl_1, br_1], [bl_2, br_2], \dots, [bl_n, br_n] $ .

Initially, all segments $ [al_i, ar_i] $ are equal to $ [l_1, r_1] $ and all segments $ [bl_i, br_i] $ are equal to $ [l_2, r_2] $ .

In one step, you can choose one segment (either from the first or from the second list) and extend it by $ 1 $ . In other words, suppose you’ve chosen segment $ [x, y] $ then you can transform it either into $ [x - 1, y] $ or into $ [x, y + 1] $ .

Let’s define a total intersection $ I $ as the sum of lengths of intersections of the corresponding pairs of segments, i.e. $ \sum\limits_{i=1}^{n}{\text{intersection_length}([al_i, ar_i], [bl_i, br_i])} $ . Empty intersection has length $ 0 $ and length of a segment $ [x, y] $ is equal to $ y - x $ .

What is the minimum number of steps you need to make $ I $ greater or equal to $ k $ ?

输入格式:

The first line contains the single integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases.

The first line of each test case contains two integers $ n $ and $ k $ ( $ 1 \le n \le 2 \cdot 10^5 $ ; $ 1 \le k \le 10^9 $ ) — the length of lists and the minimum required total intersection.

The second line of each test case contains two integers $ l_1 $ and $ r_1 $ ( $ 1 \le l_1 \le r_1 \le 10^9 $ ) — the segment all $ [al_i, ar_i] $ are equal to initially.

The third line of each test case contains two integers $ l_2 $ and $ r_2 $ ( $ 1 \le l_2 \le r_2 \le 10^9 $ ) — the segment all $ [bl_i, br_i] $ are equal to initially.

It’s guaranteed that the sum of $ n $ doesn’t exceed $ 2 \cdot 10^5 $ .

输出格式:

Print $ t $ integers — one per test case. For each test case, print the minimum number of step you need to make $ I $ greater or equal to $ k $ .

样例:

样例输入 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

3
3 5
1 2
3 4
2 1000000000
1 1
999999999 999999999
10 3
5 10
7 8

样例输出 1:

1
2
3

7
2000000000
0

思路:

实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include "ybwhead/ios.h"
int main()
{
    int TTT;
    yin >> TTT;
    while (TTT--)
    {
        long long n, k, l1, l2, r1, r2, ans;
        yin >> n >> k >> l1 >> r1 >> l2 >> r2;
        if (max(l1, l2) <= min(r1, r2))
        {
            k = max(0ll, k - n * (min(r1, r2) - max(l1, l2)));
            long long x = n * (abs(l1 - l2) + abs(r1 - r2));
            ans = min(k, x) + max(0ll, k - x) * 2;
        }
        else
        {
            long long x = max(l1, l2) - min(r1, r2);
            ans = 1e18;
            for (int i = 1; i <= n; i++)
            {
                long long sum = x * i;
                long long y = (max(r1, r2) - min(l1, l2)) * i;
                sum += min(k, y) + max(0ll, k - y) * 2;
                ans = min(ans, sum);
            }
        }
        yout << ans << endl;
    }
    return 0;
}