【題解】Codeforces 1389D. Segment Intersections

【題目敘述】http://codeforces.com/contest/1389/problem/D

#include <iostream>
using namespace std;
 
long long t, n, k, l1, r1, l2, r2, a, b, tmp, c;
long long ans;
 
int main() {
    cin >> t;
    while (t--){
        c++;
        cin >> n >> k;
        cin >> l1 >> r1 >> l2 >> r2;
        //if (c == 121) cout << n << "," << k << "," << l1 << "," << r1 << "," << l2 << "," << r2 << "\n";
        a = max(r1, r2)-min(l1, l2);
        b = min(r1, r2)-max(l1, l2);
        ans = 0;
        if (b * n >= k){
            cout << 0 << "\n";
            continue;
        }
        if (b >= 0){
            k -= b * n;
            if (a == b) ans += k*2;
            else{
                tmp = min(n, k/(a-b));
                ans = tmp * (a-b);
                k -= (a-b) * tmp;
                if (k){
                    if (tmp < n) ans += k;
                    else ans += k*2;
                }
            }
        }
        else{
            tmp = min(n, k/a);
            if (tmp == 0){
                ans += -b+k;
                cout << ans << "\n";
                continue;
            }
            ans = tmp * (a-b);
            k -= a * tmp;
            if (k){
                if (tmp < n && (k-b) <= k*2){
                    ans += (k-b);
                }
                else ans += k*2;
            }
        }
        cout << ans << "\n";
    }
}
分享本文 Share with friends