括号匹配的简单应用
各区间的权重((ri - li) * cj)之和最小
- cf-Pinely Round 3 (Div. 1 + Div. 2) 的 C题
- 解析:
构建 𝑣=𝑙1,𝑙2,…,𝑙𝑛,𝑟1,𝑟2,…,𝑟𝑛并排序。
如果用符号 (替换每个 l𝑖,
用符号 )替换每个 𝑟𝑖,就会得到一个 正则括号序列
- 现在将每个 (与 对应 )匹配。您可以证明这是重新排列 𝑙𝑖和 𝑟𝑖的最佳方法
- 实现:
//升序,满足括号的优先匹配原则
sort(l.begin(), l.end());
sort(r.begin(), r.end());
vector<int> lp(n);
for (int i = 0; i < n; i ++ )//vector<int> r, l均升序
{
int& t = r[i];
int k = lower_bound(l.begin(), l.end(), t) - (l.begin() + 1);//优先左边存在最大匹配
lp[i] = t - l[k];
l.erase(l.begin() + k);//删除栈顶,已匹配过
}
/*先模拟栈的括号匹配,获得最优区间差,后贪心得到区间权重和*/
判断圆上弦交点
- atcoder-ABC338的 E题
- 描述:圆上有2n的点,n条弦,弦连接的点各不相同,问是否相交
- 解析:
是否满足括号的优先匹配,或是否有两区间交集非空
- 实现:
v.resize(n * 2 + 1, -1);//vector的初始化, -1代表左括号
for (int i = 0; i < n; i ++ )
{
int a, b;
cin >> a >> b;
if (a > b) swap(a, b);
v[b] = a;//顺序匹配,大数指向匹配的左括号位置
}
...
bool match(vector<int>& v)
{
stack<int> p;
for (int i = 1; i <= n * 2; i ++ )
if (v[i] == -1) p.push(i);//左括号,放入栈中
else
{
if (!p.empty() && p.top() == v[i])//有元素,且栈顶匹配成功
p.pop();
else return false;//匹配失败,返回false
}
if (!p.empty()) return false;//有剩余左括号无法匹配
return true;//全部匹配成功
}