首页 > 代码库 > Samurai's Stroke
Samurai's Stroke
题目链接
- 题意:
一个长度为L的木棍,有n个支点支撑,每一个点是一个int数。表示距离木棍左端点的距离。求在那些位置将木棍劈开能够使得至少有一个木棍掉下去,输出这些位置的长度
3 ≤ l ≤ 109; 2 ≤ n ≤ 105 - 分析:
对于左端的木棍。假设会掉下去一定是重心在木棍之外。两种情况:1,在最左端木棍之外。2,在最右木棍之外
每次能够得到一个答案区间,最后再从右向左处理一下,将区间合并即答案
const int maxn = 1100000; struct Seg { int l, r; bool operator< (const Seg& rhs) const { if (l != rhs.l) return l < rhs.l; return r < rhs.r; } } x[maxn]; int tot, L, n; int ipt[maxn]; void fun(bool flag) { if (flag) x[tot++] = (Seg){ L - 2 * ipt[0], L }; else x[tot++] = (Seg){ 0, 2 * ipt[0] }; REP(i, n - 1) { int l = ipt[i] * 2, r = ipt[i + 1]; if (l <= r) { if (flag) x[tot++] = (Seg){ L - r, L - l }; else x[tot++] = (Seg){ l, r }; } } } int main() { while (~RII(L, n)) { tot = 0; REP(i, n) RI(ipt[i]); sort(ipt, ipt + n); fun(false); REP(i, n) ipt[i] = L - ipt[i]; sort(ipt, ipt + n); fun(true); sort(x, x + tot); int cnt = 1; FF(i, 1, tot) { int &l1 = x[cnt - 1].l, &r1 = x[cnt - 1].r; int &l2 = x[i].l, &r2 = x[i].r; if (r1 >= l2) { r1 = max(r1, r2); } else { x[cnt].l = l2; x[cnt].r = r2; cnt++; } } tot = cnt; int ans = 0; REP(i, tot) { ans += x[i].r - x[i].l; } WI(ans); } return 0; }
Samurai's Stroke
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。