AT_arc205_c 题解

题目大意

洛谷题面有点问题。建议看 AtCoder 的。

就是说给你

n

个人，他们要在数轴上从

s_i

走到

t_i

，然后让你找一个先后顺序，使得每个人走的时候不会遇到人，或报告无解。

赛时以为只有样例 2 的情况是无解的，假了但竟然 A 掉了，嘻嘻。

考虑什么情况下无解。

按

s_i

排序，如果有一个

i

满足

t_i > t_{i + 1}

就是无解。

就是两种情况。一种是我赛时想到的方向不同的路线有交叉无解。还有就是出现包含关系的无解。都可以被上面的方法判掉，很巧妙。

我们把向右走的从大到小排序，把向左走的从小到大排序。其实按哪个端点排无所谓，因为不可能出现包含的情况，无解已经判过了。

然后因为方向不同的路线不会出现交叉（同理，无解判过了），所以哪个方向的先走也无所谓。只要保证向右走的大的先走，向左走的小的先走就行了。

AC Code

CPP

#include<bits/stdc++.h>
#define int long long
#define r(x) for (int i = 1; i <= x; i++)
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define reb(i, a, b) for (int i = a; i >= b; i--)
using namespace std;

const int N = 5e5 + 50;
int n, s, t, cntl, cntr;
pair<int, int> p[N], l[N], r[N];

signed main()
{
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	r(n)
	{
		cin >> s >> t;
		p[i] = make_pair(s, t);
		if (s < t) l[++cntl] = make_pair(-s, i);
		// 懒得写 cmp 所以直接变负数就是从大到小排了 
		else r[++cntr] = make_pair(s, i); 
	}
	sort(p + 1, p + n + 1);
	sort(l + 1, l + cntl + 1);
	sort(r + 1, r + cntr + 1);
	r(n - 1) if (p[i].second > p[i + 1].second)	
		return cout << "No", 0;
	cout << "Yes\n";
	r(cntl) cout << l[i].second << " ";
	r(cntr) cout << r[i].second << " ";
	return 0;
}

文章操作

相关推荐

评论

AT_arc205_c 题解