T25353: 排队

greedy, http://cs101.openjudge.cn/practice/25353

思路：

一个自然的想法是从前到后逐个确定当前位置可以填入的身高最小的同学。
如果现在一个同学 $i$ 想要前移到当前位置，则 $∄ j < i, s.t. | h_{i} - h_{j} | > D$ 。
因此可以发现：当且仅当 $i$ 前面“卡住它”的 $j$ 都已经被移到最前面的一些位置并固定下来， $i$ 才能前移到当前位置。
算法一：确定每一个位置时，暴力枚举待确定位置的同学，找到能前移且身高最小者即可。时间复杂度为 $O (n^{2})$ 。
算法二：注意到这是一个图论模型，考虑一个 $n$ 个点的图，对初始序列中满足 $j < i \land | h_{i} - h_{j} | > D$ 的 $(i, j)$ ，连有向边 $j \to i$ ，维护优先队列拓扑排序即可。时间复杂度为 $O (n^{2})$ 。
算法三：注意到每个连向 $i$ 的 $j$ 满足 $j < i, h_{j} < h_{i} - D$ 或 $j < i, h_{j} > h_{i} + D$ ，AI 说这个可以“线段树优化建图”，点数和边数都将变为 $O (n \log n)$ 。对原图上的点用优先队列维护、对“优化建图”中新建的点用普通队列维护即可。时间复杂度为 $O (n \log n)$ 。
算法四：考虑不要把“图”建出来。注意到这张图是“分层”的，即我们可以把所有同学分成若干层，使得将层内排序结果拼起来就能得到答案。
这个结论看上去似乎比较“直观”，比如样例中 $1, 2, 4$ 和 $3, 5$ 就是两层，层内可以任意交换；但总让人有点不安，下面我们来证明一下。
在某一时刻，设待确定者中没有“被卡住”的同学编号为 $x_{1} < x_{2} < \dots < x_{k}$ ，则 $(x_{1}, x_{2}), \dots, (x_{k - 1}, x_{k}), (x_{k}, n]$ 这些区间中每个同学都至少被前面的一个同学卡住。
(1) 对 $(x_{k}, n]$ 中的同学，它们显然不能在这些没有“被卡住”的同学都前移之前前移。
(2) 而对于 $(x_{1}, x_{k})$ 中的同学，考虑反证法，即对目前被卡住的同学 $t \in (x_{i}, x_{i + 1})$ ，当某些没有“被卡住”的同学 $x_{j} (j \leq i)$ 移到最前面并固定下来时，假设 $t$ 不再“被剩下的项卡住”，则可知 $| h_{t} - h_{x_{j}} | > d$ ，又由于 $| h_{x_{i + 1}} - h_{x_{j}} | \leq d, | h_{x_{i + 1}} - h_{t} | \leq d$ ，可得 $h_{t} > h_{x_{i + 1}} > h_{x_{j}}$ 或 $h_{x_{j}} > h_{x_{i + 1}} > h_{t}$ 。若为前者，则此时取 $t$ 不优；若为后者，则矛盾，因为取 $h_{x_{j}}$ 不优于 $h_{x_{i + 1}}$ ，即我们前移 $x_{j}$ 的操作不优。
故 (1)(2) 均不成立，可知上面的结论正确。
通过支持单点修改、前 / 后缀最大值的树状数组，即可从前到后依次求出每个同学所处的层。时间复杂度为 $O (n \log n)$ 。

代码（算法三）：

cpp

#include <algorithm>
#include <queue>
#include <cstdio>

using namespace std;

struct Node {
	int ls;
	int rs;
};

struct Edge {
	int nxt;
	int end;
};

struct Candidate {
	int pos;

	Candidate(int _pos) : pos(_pos) {}
};

int n, id, root = 0, cnt = 0;
int h[1900001], lsh[100001], head[1900001], deg[1900001];
Node tree[1900001];
Edge edge[7100001];
queue<int> q;
priority_queue<Candidate> pq;

bool operator <(const Candidate a, const Candidate b){
	return h[a.pos] > h[b.pos];
}

void add_edge(int start, int end){
	cnt++;
	edge[cnt].nxt = head[start];
	head[start] = cnt;
	edge[cnt].end = end;
	deg[end]++;
}

int insert(int x, int l, int r, int val, int pos){
	int ans = ++id;
	tree[ans] = tree[x];
	if (x != 0) add_edge(x, ans);
	add_edge(pos, ans);
	if (l == r) return ans;
	int mid = (l + r) >> 1, &ls = tree[ans].ls, &rs = tree[ans].rs;
	if (val <= mid){
		ls = insert(ls, l, mid, val, pos);
	} else {
		rs = insert(rs, mid + 1, r, val, pos);
	}
	return ans;
}

void add_edges(int x, int L, int R, int l, int r, int pos){
	if (x == 0) return;
	if (l <= L && R <= r){
		add_edge(x, pos);
		return;
	}
	int mid = (L + R) >> 1;
	if (l <= mid) add_edges(tree[x].ls, L, mid, l, r, pos);
	if (r > mid) add_edges(tree[x].rs, mid + 1, R, l, r, pos);
}

void push(int x){
	if (x <= n){
		pq.push(Candidate(x));
	} else {
		q.push(x);
	}
}

bool empty(){
	return q.empty() && pq.empty();
}

int pop(){
	int ans;
	if (!q.empty()){
		ans = q.front();
		q.pop();
	} else {
		ans = pq.top().pos;
		pq.pop();
	}
	return ans;
}

int main(){
	int d, m;
	scanf("%d %d", &n, &d);
	for (int i = 1; i <= n; i++){
		scanf("%d", &h[i]);
		lsh[i] = h[i];
	}
	sort(lsh + 1, lsh + n + 1);
	m = unique(lsh + 1, lsh + n + 1) - lsh - 1;
	id = n;
	for (int i = 1; i <= n; i++){
		int r = upper_bound(lsh + 1, lsh + m + 1, h[i] - d - 1) - lsh - 1, l = lower_bound(lsh + 1, lsh + m + 1, h[i] + d + 1) - lsh;
		if (r >= 1) add_edges(root, 1, m, 1, r, i);
		if (l <= m) add_edges(root, 1, m, l, m, i);
		root = insert(root, 1, m, lower_bound(lsh + 1, lsh + m + 1, h[i]) - lsh, i);
	}
	for (int i = 1; i <= id; i++){
		if (deg[i] == 0) push(i);
	}
	while (!empty()){
		int cur = pop();
		if (cur <= n) printf("%d\n", h[cur]);
		for (int i = head[cur]; i != 0; i = edge[i].nxt){
			int x = edge[i].end;
			if (--deg[x] == 0) push(x);
		}
	}
	return 0;
}

思路：两个月前就尝试过一直不会做，现在还是不会做，学习了树状数组后靠ai写了一个出来。。。

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <map>
using namespace std;

int lowbit(int x){
    return x&(-x);
}
class BIT {
private:
    vector<int> depth;
    int length;
public:
    BIT(int len) : length(len){
        depth.resize(len,-1);
    }
    void update(int id,int newvalue){
        while(id<=length){
            depth[id-1]=max(depth[id-1],newvalue);
            id+=lowbit(id);
        }
    }
    int findmax(int id){
        int f=-1;
        while(id>0){
            f=max(f,depth[id-1]);
            id-=lowbit(id);
        }
        return f;
    }
};
int main(){
    int n,d;
    cin>>n>>d;
    vector<int> heights(n,0);
    for(int i=0;i<n;i++){
        cin>>heights[i];
    }
    vector<int> sortheights=heights;
    sort(sortheights.begin(),sortheights.end());
    sortheights.erase(unique(sortheights.begin(),sortheights.end()),sortheights.end());
    int t=sortheights.size();
    unordered_map<int,int> mp;
    for(int i=0;i<t;i++){
        mp[sortheights[i]]=i;
    }
    BIT stree(t);
    BIT rtree(t);
    map<int,vector<int>> depclass;
    for(int height : heights){
        int sortid=upper_bound(sortheights.begin(),sortheights.end(),height-d-1)-sortheights.begin();
        int rsortid=t-(lower_bound(sortheights.begin(),sortheights.end(),height+d+1)-sortheights.begin());
        int max1=stree.findmax(sortid);
        int max2=rtree.findmax(rsortid);
        int de=max(max1,max2)+1;

        stree.update(mp[height]+1,de);
        rtree.update(t-mp[height],de);
        depclass[de].push_back(height);
    }
    for(auto &p:depclass){
        sort(p.second.begin(),p.second.end());
        for(int height : p.second){
            cout<<height<<'\n';
        }
    }
    return 0;
}

思路：用链表实现元素删除的O(1)实现就过了，本来用vector元素删除O(N)就过不了

cpp

#include <bits/stdc++.h>

using namespace std;

struct lineup

{

    long long height;

    lineup *next;
};

int main()
{

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, D;

    cin >> N >> D;

    vector<lineup> stu(N);

    for (int i = 0; i < N - 1; i++)
    {

        long long h;

        cin >> h;

        stu[i] = {h, &stu[i + 1]};
    }

    cin >> stu[N - 1].height;

    stu[N - 1].next = NULL;

    lineup *head = &stu[0];

    multiset<long long> part;

    vector<long long> ans;

    while (head->next != NULL)
    {

        lineup *it = head;

        lineup *previous = head;

        bool flag = 1;

        long long mmin = it->height, mmax = it->height;

        while (it != NULL)
        {

            mmin = min(mmin, it->height);

            mmax = max(mmax, it->height);

            if (abs(it->height - mmin) <= D && abs(it->height - mmax) <= D)
            {

                part.insert(it->height);

                previous->next = it->next;
            }

            else
            {

                if (flag)
                {
                    head = it;
                    flag = 0;
                }

                previous = it;
            }

            it = it->next;
        }

        while (!part.empty())
        {
            ans.push_back(*part.begin());
            part.erase(part.begin());
        }


    }

    //ans.push_back(head->height);

    for (int i = 0; i < N; i++) cout << ans[i] << '\n';
}

对于这道题目，线段树（或类似的二分查找树）思路实际上是解决这个问题的正解方向之一。这个问题的本质是求一个字典序最小的拓扑排序，而由于约束条件的特殊性（ $| h_{i} - h_{j} | > D$ 时不能交换），这可以转化为一个分层问题：每一个数 $h_{i}$ 必须排在所有在该数之前出现、且与该数差值超过 $D$ 的数之后。

代码使用了动态开点的线段树思想（尽管是一次性建树），维护的是“值域”上的最大层数。

如果得到 WA（Wrong Answer）的主要原因很可能是 整数溢出 以及 I/O 速度 问题，还有 getf 函数中对于“完全包含在安全区”的节点处理不够显式（虽然逻辑上勉强通过，但为了稳健性最好加上）。

1. 整数溢出问题 (Critical)

题目中 $h_{i}$ 和 $D$ 均可达 $10^{9}$ 。在代码中调用 getf(h[i] - d, h[i] + d, root) 时： h[i] + d 的计算结果最大可达 $2 \times 10^{9}$ 。虽然 $2 \times 10^{9}$ 刚好在 int (约为 $2.147 \times 10^{9}$ ) 的范围内，但非常接近边界。如果测试数据稍微触碰边界，或者编译器对有符号整数溢出的处理，这都是极其危险的。更重要的是，你的 getf 函数参数定义为 const int&。如果计算结果发生了溢出（变成负数），或者单纯因为类型转换问题，会导致 ub 变成一个很小的数，从而导致 cur->l > ub 误判为真，返回错误的层数。

修改建议： 将 getf 的参数改为 long long，并在调用时强制转换计算类型。

2. 递归查询的逻辑隐患

在 getf 函数中，你通过 cur->r < lb 和 cur->l > ub 来判断是否落在“阻挡区”。如果一个节点的区间 [l, r] 完全落在 [lb, ub]（安全区，即可以交换的区域）内，你的代码通过不进入 if 分支最终返回 ans = -1。这个逻辑是对的，但是为了清晰和防止边界错误，最好显式处理“无交集”或“被包含”的情况。

3. I/O 性能

$N = 10^{5}$ ，且输出量大，使用 cin/cout 而不加 ios::sync_with_stdio(0) 极易导致 TLE（虽然你报的是 WA，但有时候评测机反馈不准确，或者因为超时截断导致 WA）。

long long 的使用，增加了 Fast I/O。

cpp

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct Node {
    int f;          // 当前区间的最大批次
    int l, r;       // 当前结点覆盖的值域 [l, r]
    Node* l_ch;
    Node* r_ch;
    
    Node(int a, int b, int x = -1) : f(x), l(a), r(b), l_ch(nullptr), r_ch(nullptr) {}
};

// 建树逻辑不变，注意这里是对排序后的值建树
Node* buildTree(const vector<int>& v, int l, int r) {
    if (v[l] == v[r]) return new Node(v[l], v[r]); // 这里的区间是值域
    int m = l + (r - l) / 2;
    Node* cur = new Node(v[l], v[r]);
    cur->l_ch = buildTree(v, l, m);
    cur->r_ch = buildTree(v, m + 1, r);
    return cur;
}

// 查询范围 [lb, ub] 之外（即 (-inf, lb) U (ub, inf)）的最大 f 值
// 使用 long long 避免 lb/ub 溢出问题
int getf(long long lb, long long ub, Node* cur) {
    // 如果当前节点完全在安全区 [lb, ub] 内，它不产生阻挡，忽略
    if (cur->l >= lb && cur->r <= ub) return -1;
    
    // 如果当前节点完全在左侧阻挡区 (-inf, lb)
    if (cur->r < lb) return cur->f;
    // 如果当前节点完全在右侧阻挡区 (ub, inf)
    if (cur->l > ub) return cur->f;

    // 否则区间有重叠，需要递归查询
    int ans = -1;
    if (cur->l_ch) ans = max(ans, getf(lb, ub, cur->l_ch));
    if (cur->r_ch) ans = max(ans, getf(lb, ub, cur->r_ch));
    
    return ans;
}

// 更新值为 k 的节点的层数为 nf
void updatef(int k, int nf, Node* cur) {
    // 找到覆盖 k 的叶子节点（或者值域缩成一点的节点）
    if (cur->l == k && cur->r == k) {
        cur->f = max(cur->f, nf);
        return;
    }
    
    // 递归更新子节点
    // 由于可能有重复值，且树的划分是基于排序后的索引，相同的值可能跨越左右子树
    // 因此需要分别检查
    if (cur->l_ch && k <= cur->l_ch->r) updatef(k, nf, cur->l_ch);
    if (cur->r_ch && k >= cur->r_ch->l) updatef(k, nf, cur->r_ch);
    
    // 回溯更新当前节点
    int val = -1;
    if (cur->l_ch) val = max(val, cur->l_ch->f);
    if (cur->r_ch) val = max(val, cur->r_ch->f);
    cur->f = val;
}

int main() {
    // 开启 Fast I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long d; // D 可能很大，配合加法运算使用 long long
    if (!(cin >> n >> d)) return 0;

    vector<int> h(n);
    for(int i = 0; i < n; i++) cin >> h[i];

    // 排序并建树
    vector<int> sorted_h(h);
    sort(sorted_h.begin(), sorted_h.end());
    
    // 构建线段树
    Node* root = buildTree(sorted_h, 0, n - 1);

    // 存储分层结果
    // fs[layer] 存储该层所有的身高
    vector<vector<int>> fs; 

    for(int i = 0; i < n; i++) {
        // 查询阻挡区：(-inf, h[i]-d) U (h[i]+d, inf)
        // 计算 h[i]-d 和 h[i]+d 时强制使用 long long
        long long lb = (long long)h[i] - d;
        long long ub = (long long)h[i] + d;
        
        int nf = getf(lb, ub, root) + 1;
        
        updatef(h[i], nf, root);

        if (fs.size() <= nf) {
            fs.resize(nf + 1);
        }
        fs[nf].push_back(h[i]);
    }

    // 输出
    for(auto& group : fs) {
        sort(group.begin(), group.end()); // 同一层内按身高从小到大排序（字典序最小）
        for(int val : group) {
            cout << val << "\n";
        }
    }

    return 0;
}

【潘彦璋物理学院】思路：终于写到这里……我在这题上花了超久，首先是用的我在课后与同学初步讨论得到的拓扑排序解法，直接显式建图，记录每个点的所有儿子，入度，值，然后把所有入度为0的点丢到一个最小堆（我还为此学了一下堆如何自定义比较规则）blablabla……结果不出意料的爆了，而且还是先爆的内存，因为我把所有子结点指针直接存在结点里，但是其实只要存子结点的编号就够了然后就是喜闻乐见的优化环节，首先这个拓扑排序的思路优化空间不说前途光明也是一点没有，于是只能求教AI和同学，于是收获了一个新思路：分层。分层的主要思路是多次扫描数列h_i，每次找出所有入度为0的点，然后将他们一并删去，随后循环直到处理完所有数据。这个做法与每次只删去一个点相比利用了一个好的性质，那就是在任意时刻所有入度为0的点在最后的输出中必定是连续的。证明如下：首先找出某一时刻数列中所有入度为0的点（编号为{a_1~a_n}，满足h_a_i单调递增），如果他们在最后的结果中不连续，那只能是在从小到大依次删除他们的过程中会产生新的入度为0的点，且其值小于h_a_n。假设这样的点a_k在删除a_i时产生，则有h_a_k大于h_a_i + D或h_a_k小于h_a_i - D。 1 若h_a_k大于h_a_i + D：由于h_a_n和h_a_k可以交换，故h_a_n不大于h_a_i + D，所以h_a_k不可能小于h_a_n，矛盾 2 若h_a_k小于h_a_i - D：则h_a_n和h_a_k的差必然大于D，因此a_n与a_k之间存在边，要么a_n入度不为零要么a_k入度不为零，总之矛盾因此，问题就变成了将所有数据分批，而且一个点的输出批次只与其前面的输入数据有关，只要知道了输出的批次就可以得到结果。又注意到某个点的输出批次等于它前面的与其值相差大于D的所有点的批次中的最大值+1（没有找到就是0），于是我们可以使用线段树维护每个区间点的批次最大值。于是本人去学习了线段树的写法，然后又是指针显式建树（用数组应该也可以，但是我不太会，用指针更明了），最后终于是搞出来了，但是还是败在细节上了，递归访问的逻辑写错了…… 总之，现在基本是会写线段树了，但是还得练习。另外最后为了调试debug把注释基本全写上了，可以给同学参考了（

cpp

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

struct Node {
    int f, l, r; //f储存当前区间的最大批次，l和r则是当前区间的值域左右端
    Node* l_ch;
    Node* r_ch;
    Node(int a, int b, int x = -1) : f(x), l(a), r(b), l_ch(nullptr), r_ch(nullptr) {} //未处理的结点默认批次为-1，方便后续处理
};

Node* buildTree(vector<int>& v, int l, int r) {
    if(v[l] == v[r]) return (new Node(v[l], v[r])); //值相同的点可以合并储存
    int m = l + (r - l) / 2; //简单二分
    Node* cur = (new Node(v[l], v[r]));
    cur->l_ch = buildTree(v, l ,m);
    cur->r_ch = buildTree(v, m + 1, r); //树的建立过程保证了所有非叶子结点都有左右孩子
    return cur;
}

int getf(const int& lb, const int& ub, Node* cur) {
    if (cur->l >= lb && cur->r <= ub) return -1; //当前节点区间完全在[lb, ub]内
    if(cur->r < lb) return cur->f; //当前结点的区间完全在(-无穷, lb)内
    if(cur->l > ub) return cur->f; //当前结点的区间完全在(ub, +无穷)内
    //否则有重叠，需要进一步递归
    int ans = -1;
    if(cur->l_ch) ans = max(ans, getf(lb, ub, cur->l_ch)); //执行该语句时必定有cur->r >= lb，因此不是叶子结点
    if(cur->r_ch) ans = max(ans, getf(lb, ub, cur->r_ch)); //同上
    return ans;
}

void updatef(const int& k, const int& nf, Node* cur) {
    if(cur->l == k && cur->r == k) {
        cur->f = max(cur->f, nf); //找到，更新
        return;
    }
    if(k <= cur->l_ch->r) updatef(k, nf, cur->l_ch);
    if(k >= cur->r_ch->l) updatef(k, nf, cur->r_ch);
    cur->f = max(cur->l_ch->f, cur->r_ch->f);
    return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, d;
    cin >> n >> d;
    vector<int> h(n);
    for(int i = 0; i < n; i ++) cin >> h[i];
    vector<int> sorted_h(h.begin(), h.end());
    sort(sorted_h.begin(), sorted_h.end());
    Node* root = buildTree(sorted_h, 0, n - 1); //在排序后的h[i]上建树，减少内存需求
    vector<vector<int>> fs; //分批存储输出值
    for(int i = 0; i < n; i ++) {
        int nf = getf(h[i] - d, h[i] + d, root) + 1; //这就是方便的地方：-1对应的是要么前面的点都可以换要么是不能换的还在后面，批次显然都为0
        updatef(h[i], nf, root);
        if(fs.size() < nf + 1) fs.push_back({h[i]});
        else fs[nf].push_back(h[i]);
    }
    for(auto& p : fs){
        sort(p.begin(), p.end()); //同批次可自由交换
        for(auto& t : p) cout << t << endl;
    }
    return 0;
}

T25353: 排队 ​

T25353: 排队