关于多测清空
查看原帖
关于多测清空
189351
wheneveright楼主2021/8/27 21:24

下面是我的代码

两个qwqwqwq注释行中的memset去掉就会WA,但是我明明在下面有过初始化pre和nxt啊

想不通为什么一定要加上才能AC

# include <bits/stdc++.h>
using namespace std;

const int maxn = 100005;

struct reader {
    template <typename Type>
    reader & operator >> (Type & ret) {
        int f = 1; ret = 0; char ch = getchar ();
        for (;!isdigit (ch); ch = getchar ()) if (ch == '-') f = -f;
        for (; isdigit (ch); ch = getchar ()) ret = (ret * 10) + ch - '0';
        ret *= f; return * this;
    }
} fin;

int T, n, m; long long res;
int pre[maxn], nxt[maxn];
bool vis[maxn];
long long b[maxn];
struct node {
    int pos; long long val;
    bool operator < (node p) const {
        return val > p.val;
    }
} a[maxn];
priority_queue < node > que;

int get () {
    while (true) {
        node now = que.top (); que.pop ();
        if (vis[now.pos]) continue; return now.pos;
    }
}
void del (int id) {
    nxt[pre[id]] = nxt[id];
    pre[nxt[id]] = pre[id];
    vis[id] = true; return ;
}

int main () {
	fin >> T;
	while (T--) {
		// qwqwqwqwq
		memset (pre, 0, sizeof pre);
		memset (nxt, 0, sizeof nxt);
		// qwqwqwqwq
	    fin >> n >> m; while (!que.empty ()) que.pop (); res = 0;
	    for (int i = 1; i <= n; i++) fin >> b[i], vis[i] = false;
	    for (int i = n; i >= 2; i--) b[i] -= b[i - 1]; a[0].val = a[n--].val = 576460752303423488;
	    for (int i = 1; i <= n; i++) a[i].val = b[i + 1], a[i].pos = i, que.push (a[i]);
	    for (int i = 1; i <= n; i++) pre[i] = i - 1, nxt[i] = i + 1;
	    for (int i = 1; i <= m; i++) {
	        int now = get (); res += a[now].val;
	        a[now].val = a[pre[now]].val + a[nxt[now]].val - a[now].val;
	        que.push (a[now]); del (pre[now]); del (nxt[now]);
	    }
	    cout << res << endl;
	}
	return 0;
}
2021/8/27 21:24
加载中...