P11125 [ROIR 2024 Day 2] 细菌 题解

xuyifei1599 · 2025-01-09 15:43:37 · 题解

这道题读完之后我们会发现成熟的细菌数会一直乘 2，但 m \le 10 ^ 9 的数据范围就会使我们得出一个结论，在一个细菌成熟后，最多 30 秒，细菌数就会超出 m。

所以，我们就可以用这个性质，计算出最先成熟的细菌的成熟时间，以它为基础，用双指针维护整个过程，若细菌总数大于等于 m，就输出答案并结束程序

注意，有可能在第一个细菌成熟前，培养皿里的细菌数已经达到了 m，需要处理一下。

接下来是代码环节：

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct Node {
    int a, t, s;
} a[200005], b[200005];
int n, m, sum, num;
bool mark[200005];
bool cmp(Node x, Node y) {
    return x.s < y.s;
}
bool cmp1(Node x, Node y) {
    return x.a < y.a;
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i].a;
    }
    for (int i = 1; i <= n; i ++) {
        cin >> a[i].t;
        a[i].s = a[i].t + a[i].a;
        b[i].a = a[i].a;
    }
    sort(a + 1, a + 1 + n, cmp);
    sort(b + 1, b + 1 + n, cmp1);
//  for (int i = 2; i <= n; i ++) {
//      if (a[i].s - a[1].s >= 40) {
//          n = i;
//          break;
//      }
//  }
//  cout << "\n";
//  for (int i = 1; i <= n; i ++) {
//      cout << a[i].a << " " << a[i].t << "\n";
//  }
    int t = a[1].s, j = 1, k = 1;
    for (int i = 1; i <= n; i ++) {
        if (b[i].a < t) {
            if (b[i].a != b[i - 1].a) {
                if (num == m) {
                    cout << b[i - 1].a;
                    return 0;
                } else if (num > m) {
                    cout << "-1";
                    return 0;
                }
            }
            num ++;
        } else {
            if (num == m) {
                cout << b[i - 1].a;
                return 0;
            } else if (num > m) {
                cout << "-1";
                return 0;
            }
            k = i;
            break;
        }
    }
    if (b[n].a < t) {
        if (num == m) {
            cout << b[n].a;
            return 0;
        } else if (num > m) {
            cout << "-1";
            return 0;
        }
    }
    for (int i = k; i <= n; i ++) {
        if (b[i].a == t) {
            num ++;
        } else {
            k = i;
            break;
        }
    }
//  cout << num << " " << sum << "\n";
    for (int i = 1; i <= n; i ++) {
        if (a[i].s == t) {
            sum += 2;
        } else {
            j = i;
            break;
        }
    }
    num -= sum / 2;
    if (sum + num == m) {
        cout << t;
        return 0;
    }
    if (sum + num > m) {
        cout << "-1";
        return 0;
    }
    while (true) {
        t ++;
        sum *= 2;
        if (t == a[j].s) {
            for (; j <= n; j ++) {
                if (a[j].s == t) {
                    sum += 2;
                    num --;
                } else {
                    break;
                }
            }
        }
        if (t == b[k].a) {
            for (; k <= n; k ++) {
                if (b[k].a == t) {
                    num ++;
                } else {
                    break;
                }
            }
        }
        if (sum + num == m) {
            cout << t;
            return 0;
        }
        if (sum + num > m) {
//          cout << sum << " " << num << "\n";
            cout << "-1";
            return 0;
        }
//      cout << t << ": " << sum << " " << num << "\n";
    }
    return 0;
}