题解 | #小富的 idea#

小富的idea

题目链接

可以先计算出任意两点间的融合时间, 时间复杂度 $O(n^2)O(n^2)$对融合时间排序，然后从小到大枚举，如果当前时间下对应的两个点不在一个连通块中则合并连通块的个数减一；对于时间$1,10001,1000$，可以离线预处理出来每一个时间点的个数。

实现技巧：

• 将两个墨点的编程和其融合时间作为一个复合类型；
• 计算时间时应当进行上取整；
• 一开始时所有时间点的连通块个数为 $nn$;
• 更新时只需要 $t_i\leftarrow \min (t_i,r_{i-1})t\_i\; \backslash gets\; \backslash min(t\_i,r\_\{i-1\})$
• $t_{i}t\_i$ 是 $ii$ 时间点时连通块的个数；
• 对于每个询问只需要输出 $t_{T}t\_T$ 即可

容易出错的地方

• 要考虑在 $t=0t\; =\; 0$ 时已经合并的点（重合的情况）

参考代码：

#include <cmath>
#include<iostream>
#include <algorithm>
#define Dis(x) cout << #x << " = " << x << '\n'
using namespace std;

typedef long long ll;

const int N = 1e3+7;
int t[N]; // 记录每个 连通块减少的时间
int pre[N]; // 每个连通块的代表元

int find(int u){
    if(pre[u]!=u){
        pre[u] = find(pre[u]);
    }
    return pre[u];
} // 寻找每个点的代表元

int up_div(int a,int b){
    if(!b)
        return 1e9;
    return  (a+b-1)/b;
}// a div b 上取整

struct node{
    int x,y,v;
} nodes[N];

struct com_t{
    int u,v;
    int t2; // t2 记录两个点最早的相遇时刻
    // 重载比较运算符
    bool operator < (com_t n2) const{
        return t2 < n2.t2;
    }
} mer_t[N*N];

int dist(int v,int u){
    int x = nodes[u].x - nodes[v].x;
    int y = nodes[u].y - nodes[v].y;
    return x * x +y *y;
}

// 预处理
int p = 0; // 表示有多少个融合时间
void init(int n){
    for(int i =0; i <= 1000; i++){
        // 并查集和连通块个数的初始化
        pre[i] = i;
        t[i] = n;
    }
    for(int i =1; i <= n; i++){
        for(int j =i+1; j<=n; j++){
            // 计算融合时间
            int dis = dist(i,j);
            int v = nodes[i].v + nodes[j].v;
            if(v == 0) continue;
            int t2 = (int) ceil(sqrt(dis)/v);
            mer_t[p++] = {i,j,t2};
        }
    }
    sort(mer_t,mer_t+p);
    // 枚举每个融合时间
    int cnt = n; // 0 时刻 连通块个数 n
    for(int i = 0; i < p; i++){
        int u = mer_t[i].u;
        int v = mer_t[i].v;
        int t2 = mer_t[i].t2;
        u = find(u); v = find(v);
        if(u != v){
            pre[u] = v;
            // 合并只是修改代表元的父节点
            // 每次合并不同连通块中的两个点
            // 会使连通块儿的个数减少1
            t[t2] = --cnt;
        }
    }
    for(int i =1; i <= 1010; i++){
        t[i]  = min(t[i],t[i-1]);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n,q;
    cin >> n;
    for(int i =1; i <= n; i++){
        int x,y,v;
        cin >> x >> y >>v;
        nodes[i] = {x,y,v};
    }
    init(n);
    cin >> q;
    while(q--){
        int T; cin >> T;
        cout << t[T] << '\n';
    }
}