scu优先队列是什么？

本文共计716个文字，预计阅读时间需要3分钟。

Sidney想前往Gandtom家玩。但Sidney家和Gandtom家之间是高低不平、坑坑洼洼的土路。所以他需要用背包装几块破旧的砖，在路上铺平一些干燥的土，才能使路变得平整，到达Gandtom家。

Description
　　Sidney想去Gandtom家玩。但Sidney家和Gandtom家之间是高低不平、坑坑洼洼的土路。所以他需要用他的背包装几袋稀的泥，在路上铺平一些干的土，使路变成平整的泥土，才能到Gandtom家见到Gandtom。
　　已知现在有n袋稀的泥，第i袋稀的泥的质量为wi。初始时，第i个分组只有第i袋稀的泥。接下来Sidney每一次会把质量最小（如果质量相同取编号小的）的两组稀的泥合并成一组。新的分组的质量为原来两分组质量的和，编号为原来两组稀的泥的编号的较小者的编号。
　　试求Sidney经过t次操作后，第q袋稀的泥在第几组中。

Input
第一行有一个整数T，表示组数。
每组数据第一行有两个正整数n，m
，
(0

#include<iostream> #include<cstdio> #include<algorithm> #include<cstdlib> #include<cstring> #include<string> #include<cmath> #include<map> #include<set> #include<vector> #include<queue> #include<string> #include<bitset> #include<ctime> typedef long long ll; using namespace std; typedef unsigned long long int ull; #define maxn 500005 #define ms(x) memset(x,0,sizeof(x)) #define Inf 0x7fffffff #define inf 0x3f3f3f3f const long long int mod = 1e9 + 7; #define pi acos(-1.0) #define pii pair<int,int> #define eps 1e-7 #define pll pair<ll,ll> ll quickpow(ll a, ll b) { ll ans = 1; a = a % mod; while (b > 0) { if (b % 2)ans = ans * a; b = b / 2; a = a * a; } return ans; } int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); } int t[maxn], q[maxn], fa[maxn]; struct node { int id, w; node(){} node(int id, int w) :id(id), w(w) {}; bool operator < (const node &rhs)const { if (rhs.w == w)return rhs.id < id; return rhs.w < w; } }; int fath(int x) { if (x == fa[x])return x; else return fa[x] = fath(fa[x]); } int main() { //ios::sync_with_stdio(false); int tt; //cin >> tt; scanf("%d", &tt); while (tt--) { priority_queue<node>qq; int n, m, tmp; //cin >> n >> m; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { fa[i] = i; //cin >> tmp; scanf("%d", &tmp); qq.push(node(i, tmp)); } int cnt = 0; for (int i = 1; i <= m; i++) { //cin >> t[i] >> q[i]; scanf("%d%d", &t[i], &q[i]); if (cnt == t[i]) { //cout << fath(q[i]) << endl; printf("%d\n", fath(q[i])); continue; } while (cnt < t[i]) { cnt++; node fir = qq.top(); qq.pop(); node sec = qq.top(); qq.pop(); int nwid = min(fir.id, sec.id); fa[sec.id] = fa[fir.id] = fa[nwid]; qq.push(node(fa[nwid], fir.w + sec.w)); } printf("%d\n", fath(q[i])); } } }