优化算法竞赛题解析

解决算法问题提升算法能力：->算法竞赛和题解网站 #生活技巧# #学习技巧# #编程学习指南#

题意：

一共有n(<=1e5)个元素，每一个元素都有三个关键字，a，b，c现在将这些元素分给A，B，C，这些元素价值在A手中的体现为，所有元素中最大的a值，在B中则是最大b值，C也是一样的，现在要有一种分法，求A+B+C的最小值。

题解：

首先想到的是n^2的算法，首先将所有元素按照a关键字从小到大，然后在开一个数组按照b关键字排序，然后从小到大枚举a，然后标记，然后从大到小枚举b，记录c的最大值，就可以一直更新答案。

既然知道了n^2的算法，现在想是否可以优化呢？枚举a是必然的，如果从小到大枚举a，无异是在b中删除元素，那么从大到小枚举a的话，就是在b中增加元素，删除是不好处理的，那么现在从大到小枚举a，那么现在的问题是在b中优化了。

b是从小到大排了序的，那么如果要选第i个，那么就需要知道(i + 1) ~ n中c的最大值，那么现在就会发现一个单调性便是在b中，随着b的增大，c的最大值一定是不上升的。

现在考虑新增加一个元素，那么这个元素会对它前面的比他的c小的b的c的最大值造成影响，那么现在就需要知道第一个小于等于这个元素的c值的位置，然后一并更新。

怎么知道那个位置呢？二分啊QAQ。怎么区间更新呢？线段树啊QAQ。

然后现在考虑求得答案，答案的组成是A+B+C，A是通过枚举的，现在的问题是求B+C的最小值，线段树也可以一并维护B+C了，线段树也要维护一个C的最大值。

代码：

#include <cstdio>

#include <iostream>

#include <algorithm>

using namespace std;

const int N = 1e5 + 7;

int disc[N], dcnt, n, ans = 1e9 + 7;

int mi[N << 2], vc[N << 2], lz[N << 2];

struct node {int a, b, c;} ai[N];

#define mid (l + r >> 1)

#define lson o << 1, l, mid

#define rson o << 1 | 1, mid + 1, r

bool cmp (node a, node b) {return a.a < b.a;}

void pushdown (int o, int l, int r)

{

if (!lz[o]) return;

mi[o << 1] = disc[l] + lz[o], vc[o << 1] = lz[o], lz[o << 1] = lz[o];

mi[o << 1 | 1] = disc[mid + 1] + lz[o], vc[o << 1 | 1] = lz[o], lz[o << 1 | 1] = lz[o];

lz[o] = 0;

}

void update (int o, int l, int r, int L, int R, int x)

{

if (l == L && r == R)

{

mi[o] = disc[L] + x;

vc[o] = x;

lz[o] = x;

return;

}

pushdown(o, l, r);

if (R <= mid) update (lson, L, R, x);

else if (L > mid) update (rson, L, R, x);

else update (lson, L, mid, x), update (rson, mid + 1, R, x);

mi[o] = min (mi[o << 1], mi[o << 1 | 1]);

}

int query (int o, int l, int r, int x)

{

if (l == r) return vc[o];

pushdown(o, l, r);

if (x <= mid) return query (lson, x);

else if (x > mid) return query (rson, x);

}

int getpos (int l , int r, int d)

{

while (l < r)

{

if (query(1, 1, dcnt, mid) < d) r = mid;

else l = mid + 1;

}

return l;

}

void build (int o, int l, int r)

{

if (l == r)

{

mi[o] = disc[l];

return;

}

build (lson);

build (rson);

mi[o] = min (mi[o << 1], mi[o << 1 | 1]);

}

int main ()

{

scanf ("%d", &n);

for (int i = 1; i <= n; ++ i)

{

scanf ("%d%d%d", &ai[i].a, &ai[i].b, &ai[i].c);

disc[++dcnt] = ai[i].b;

}

disc[++dcnt] = 0;

sort (ai + 1, ai + 1 + n, cmp);

sort (disc + 1, disc + 1 + dcnt);

dcnt = unique (disc + 1, disc + 1 + dcnt) - disc - 1;

build (1, 1, dcnt);

ans = ai[n].a;

for (int i = n; i >= 1; -- i)

{

int p = lower_bound (disc + 1, disc + 1 + dcnt, ai[i].b) - disc;

int pos = getpos(1, p, ai[i].c);

if (pos <= p - 1) update (1, 1, dcnt, pos, p - 1, ai[i].c);

ans = min (ans, ai[i - 1].a + mi[1]);

}

cout << ans << endl;

return 0;

}

总结：

首先需要想到暴力，然后再优化就理所当然了，还有的就是要发现序列的单调性。

网址：优化算法竞赛题解析 https://www.yuejiaxmz.com/news/view/738787

相关内容

机器/深度学习模型最优化问题详解及优化算法汇总
今日头条智能升级：深度解析个性化推荐算法与全面优化用户体验
优化算法综述
毕业设计竞赛选题推荐
生活知识竞赛：生活知识竞赛考试试题（考试必看）
动态规划算法的优化技巧（转贴）
节能知识竞赛试题答案
2023年节能环保知识竞赛试题(附答案)
低碳生活竞赛题
中小学数学竞赛辅导策略

随便看看