题解与反思

有些题知道用什么算法去解决，但是不能想出来正解，算法的应用不太行。

D - K-th Nearest

思路：二分
1. 查找第k近的点，用二分。我们直接二分答案，也就是距离
2. 如何判断某个距离是否合法呢？我们就要计算出在该距离的范围内[x-d,x+d]包含多少个点。
3. 如果包含的点数cnt>=k, 说明这个距离包含的点数可能刚刚好也可能多了，我们缩小右端点；反之，增大左端点。
4. 为啥包含的点数大于等于k，能够说明这个距离是第k近的点，或者更多呢，图片解析。
5. 二分的范围:r=2e8+10, 因为点的坐标范围是[-1e8, 1e8],为了能够涵盖所有的点，我们应该取2e8 + 10
Code

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
int a[N];
int n, q;
bool check(int mid, int b, int k)
{
    // 求解[b-mid, b+mid] 包含多少个点
    int l = lower_bound(a, a + n, b - mid) - a;
    int r = upper_bound(a, a + n, b + mid) - a;
    int cnt = r - l;
    if(cnt >= k) return true;
    return false;
}
signed main()
{
    cin >> n >> q;
    for(int i = 0; i < n; i ++)
    {
        cin >> a[i];
    }
    sort(a, a + n);
    while(q --)
    {
        int x, k;
        cin >> x >> k;
        int l = 0, r = 2e8 + 10;
        while(l < r)
        {
            int mid = (l + r) / 2;
            if(check(mid, x, k)) r = mid;
            else l = mid + 1;
        }
        cout << r << endl;
    }
    return 0;
}

E - Maximum Glutton

思路：
1. 一个很明显的二维背包，但是如果直接二维背包好像又不太对，因为x和y的范围太大了，空间和时间都会超。
2. 但是我们又发现n特别小，所以我们可以使用交换键值法，f[i][j][k]表示前i道菜吃了j道，总甜度值为不超过k时的咸度值。维护的过程中我们尽量保持咸度值最小即可。
3. 最终的答案，枚举咸度值不超过y时最多吃几个，注意咸度值为y时，我们还可以再吃一个。
4. 状态表示：f[i][j][k]表示前i道菜吃了j道，总甜度值为不超过k时的咸度值；属性：最小值
5. 状态转移：(1)不吃第i个菜：[i][j][k] = f[i - 1][j][k];
  
  (2)吃第i个菜：f[i][j][k] = min(f[i][j][k], f[i - 1][j - 1][k - a[i]] + b[i]);
Code

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e4 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
int a[100], b[100];
int f[100][100][N];//表示考虑前i个食物，吃了j个，甜度不超过x的，最小咸度
signed main()
{
    int n, x, y;
    cin >> n >> x >> y;
    for(int i = 1; i <= n; i ++) cin >> a[i] >> b[i];
    memset(f, 0x3f, sizeof f);
    f[0][0][0] = 0;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 0; j <= i;  j ++)
        {
            for(int k = 0; k <= x; k ++)
            {
                //不吃第i个
                f[i][j][k]  = f[i - 1][j][k];
                //吃第i个
                if(k >= a[i] && j >= 1)
                {
                    f[i][j][k] = 
                        min(f[i][j][k], f[i - 1][j - 1][k - a[i]] + b[i]);
                }
            }
        }
    }
    int res = 0;
    for(int i = 0; i <= n; i ++)
    {
        for(int j = 0; j <= x; j ++)
        {
            if(f[n][i][j] <= y )
            {
               res = max(res, min(i + 1, n));
            }
        }
    }
    cout << res << endl;
    return 0;
}

F - Range Connect MST

思路：
1. 是否构成连通块，即这 $q$ 个线段是否构成一个大线段。
2. 考虑最小生成树怎么求，即考虑前 $n$ 个点该和哪个操作点 $(n i)$ 连边。
3. 从代价小的操作开始，给 $Li≤j≤Ri$ 中的每个点合并成一个联通块，每合并一次的代价是 $Ci$ 。最后看是否是同个连通块即可。
4. 连通块就用并查集维护，合并时总是以编号大的点为根，这样在上述从左到右合并时每次都从还未连通的点开始遍历，而不用遍历 $Li→Ri$ 了。
Code

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
int fa[N];
vector<vector<int>> a(N, vector<int>(3));
bool cmp(const vector<int>& a, const vector<int>& b)
{
    return a[2] < b[2];
}
int find(int x)
{
    if(x != fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}
signed main()
{

    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; i ++) fa[i] = i;
    for(int i = 0; i < q; i ++) cin >> a[i][0] >> a[i][1] >> a[i][2];
    //根据a[i][2]进行排序，也就是权值
    sort(a.begin(), a.begin() + q, cmp);
    int res = 0, cnt = n;
    
    for(int i = 0; i < q; i ++)
    {
        int l = a[i][0], r = a[i][1], c = a[i][2];
        res += c;//把该点和连通块连接
        // j = find(j) + 1, 从还未连通的点开始遍历
        for(int j = find(l) + 1; j <= r; j = find(j) + 1)
        {
            //以编号大的为根
            fa[j - 1] = j;
            cnt --;
            res += c;
        }
    }
    //如果可以合并n - 1次，那么就是连通的
    if(cnt == 1) cout << res << endl;
    else cout << -1 << endl;
    return 0;
}

AtCoder Beginner Contest 364

题解与反思

D - K-th Nearest

E - Maximum Glutton

F - Range Connect MST