【每日一题】Problem 253B. Physics Practical

原题

解决思路

1. 定义 \(dp[i][j]\) 为对 \(i\) 元素做出选择后，要删除的最少元素个数
2. 对于 \(i\)，有两种情况，选或不选
   1. 选：则找到 \(y(y>2x)\) 的个数，可以通过排序二分实现
   2. 不选：则在 \(i-1\) 的最少删除个数的选择下 \(+1\)

#include <bits/stdc++.h>

int binarySearch(std::vector<int> &a, int target) {
    int l, r; l = 0, r = a.size() - 1;
    while (l <= r) {
        int mid = (r - l) / 2 + l;
        if (a[mid] <= target) l = mid + 1;
        else r = mid - 1;
    }
    return l;
}

int main() {
    std::freopen("input.txt", "r", stdin);
    std::freopen("output.txt", "w", stdout);

    int n;
    std::cin >> n;
    std::vector<int> c(n + 1, 0);
    for (int i = 1; i <= n; ++i) std::cin >> c[i];

    std::sort(c.begin() + 1, c.end());
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(2, 0));
    int index = binarySearch(c, c[1] * 2);
    dp[1][0] = 1;
    dp[1][1] = c.size() - index;
    for (int i = 2; i <= n; ++i) {
        index = binarySearch(c, c[i] * 2);
        dp[i][0] = std::min(dp[i - 1][0], dp[i - 1][1]) + 1;
        dp[i][1] = std::min(int(c.size()) - index + dp[i - 1][0], dp[i - 1][1]);
    }

    std::cout << std::min(dp[n][0], dp[n][1]) << std::endl;
}

更好的解

将二维数组替换为一维滚动数组

• 需要注意的是，\(dp[0]\) 和 \(dp[1]\) 都相互依赖对方更新前的值，因此需要先做一次备份

#include <bits/stdc++.h>

int binarySearch(std::vector<int> &a, int target) {
    int l, r; l = 0, r = a.size() - 1;
    while (l <= r) {
        int mid = (r - l) / 2 + l;
        if (a[mid] <= target) l = mid + 1;
        else r = mid - 1;
    }
    return l;
}

int main() {
    std::freopen("input.txt", "r", stdin);
    std::freopen("output.txt", "w", stdout);

    int n;
    std::cin >> n;
    std::vector<int> c(n + 1, 0);
    for (int i = 1; i <= n; ++i) std::cin >> c[i];

    std::sort(c.begin() + 1, c.end());
    std::vector<int> dp(2, 0);
    dp[1] = n + 1;
    for (int i = 1; i <= n; ++i) {
        int index = binarySearch(c, c[i] * 2);
        int t = dp[0]; // dp[1] 依赖更新前的 dp[0], 做一层备份
        dp[0] = std::min(dp[0], dp[1]) + 1;
        dp[1] = std::min(int(c.size()) - index + t, dp[1]);
    }

    std::cout << std::min(dp[0], dp[1]) << std::endl;
}