F Hamburger Steak

题意

有 ​ 块牛排，编号为 ​，编号为 ​ 的牛排需要煎满 ​，并且每块牛排最多只能被两个锅煎，一共有 ​ 个锅，问煎玩牛排需要的最短时间

考虑计算最小的锅使用时间的最大值，然后依次暴力去凑即可。

#include <bits/stdc++.h>
using namespace std;
#define int ll
#define rep(i, j, k) for (int i = j; i <= k; ++i)
#define rrep(i, j, k) for (int i = j; i >= k; i--)
typedef long long ll;
const int N = 1e5 + 7;
struct ans {
    int k, l, r;
    void print() { cout << k << ' ' << l << ' ' << r << ' '; }
};
struct steak {
    int t, p;
    vector<ans> res;
    void print() {
        rrep(i, res.size() - 1, 0) res[i].print();
        cout << '\n';
    }
} a[N];
signed main() {
    int n, m, mx = 0, sum = 0;
    cin >> n >> m;
    rep(i, 1, n) cin >> a[i].t, a[i].p = i, sum += a[i].t, mx = max(mx, a[i].t);
    mx = max(mx, sum / m + (sum % m != 0));
    int last = 0, p = 1;
    rep(i, 1, m) {
        // last 表示当前距离凑到最大值还剩下多少，time 表示什么时候开始煎的
        int last = mx - a[p].t, time = a[p].t;
        a[p].res.push_back({i, 0, a[p].t});
        p++;
        while (last > 0 and p <= n) 
            if (a[p].t > last) {
                a[p].res.push_back({i, time, mx});
                a[p].t -= last;
                last = 0;
            } else {
                last -= a[p].t;
                a[p].res.push_back({i, time, time + a[p].t});
                time += a[p++].t;
            }
        if (p > n)
            break;
    }
    rep(i, 1, n) cout << a[i].res.size() << ' ', a[i].print();
    return 0;
}

I Intervals on the Ring

题意

一个长度为 的圆排列上有 段连续区间，现要构造 个连续区间，使得这 个连续区间的交集为的圆排列上的 段连续区间

先考虑圆排列上有 ​​​​​​​​​​ 段连续区间时，假设为 ​​​​​​​​​​​，那么很显然选择 ​​​​​​​​​​

对应的 ​​，选择 ​ 如此发现，选择的区间一定为某个区间的起点，到对应的最后区间的右端点即可。

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define rep(i, j, k) for (ll(i) = (j); (i) <= (k); (++i))
#define mem(x, y) memset(x, y, sizeof(x))
typedef long long ll;
typedef vector<ll> vll;
const int N = 1e5 + 7;
ll a[N];
vll L, R;
void solve() {
    mem(a, 0);
    L.clear(), R.clear();
    int n, m, l, r;
    cin >> n >> m;
    while (m--) {
        cin >> l >> r;
        if (l > r)
            a[l]++, a[n + 1]--, a[1]++, a[r + 1]--;
        else
            a[l]++, a[r + 1]--;
    }
    // 合并重合区间
    rep(i, 1, n) a[i] = a[i - 1] + a[i];
    rep(i, 1, n) {
        if (a[i - 1] <= 0 and a[i] > 0)
            L.emplace_back(i);
        if (a[i] > 0 and a[i + 1] <= 0)
            R.emplace_back(i);
    }
    int len = L.size();
    cout << len << endl;
    rep(i, 0, len - 1) cout << L[i] << ' ' << R[(len - 1 + i) % len] << endl;
}
signed main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}