DAY5共2题：

  • 储物点的距离（前缀和）

  • 糖糖别胡说，我真的不是签到题目（multiset，思维）

? 作者：Eriktse
? 简介：19岁，211计算机在读，现役ACM银牌选手?力争以通俗易懂的方式讲解算法！❤️欢迎关注我，一起交流C++/Python算法。（优质好文持续更新中……）?
? 原文链接（阅读原文获得更好阅读体验）：https://www.eriktse.com/algorithm/1096.html

储物点的距离

题目链接：https://ac.nowcoder.com/acm/problem/14683

预处理出各点搬运到点1和点n的代价前缀和，以及区间重量和。

假如我们要将区间[5, 7]的物品全部搬运到3，代价应该是区间[5, 7]的物品全部搬运到的1，然后减去多搬的代价：[5, 7]的重量和 * dist(1, 3)。

上面是x < l的情况，x > r的情况类似。

当l <= x <= r只需将区间[l, r]分为两部分求和即可。

记得取模，距离要取模，前缀和也要取模。

#include #define int long longusing namespace std;const int maxn = 2e5 + 9, p = 1e9 + 7;//sum_l[i]表示区间[1, i]的物品都运到点1的代价之和//prefix_a[i]表示区间[1, i]的物品重量之和//pos[i]是第i个点的位置，通过a[]作前缀和得到int a[maxn], pos[maxn], sum_l[maxn], sum_r[maxn], prefix_a[maxn];int n, m;//取模函数int mo(int x){return (x % p + p) % p;}int f(int x, int l, int r){    if(l > r)return 0;    int res = 0;    if(x = r)    {        res = mo(sum_r[r] - sum_r[l - 1]);        res = mo(res - mo(pos[n] - pos[x]) * mo(prefix_a[r] - prefix_a[l - 1]) % p);    }    return res;}signed main(){    scanf("%lld %lld",&n, &m);    pos[1] = 1;    for(int i = 2, d;i <= n; ++ i)scanf("%lld", &d), pos[i] = pos[i - 1] + d;    for(int i = 1;i <= n; ++ i)scanf("%lld", a + i);        for(int i = 1;i <= n; ++ i)    {        sum_l[i] = mo(sum_l[i - 1] + a[i] * mo(pos[i] - pos[1]) % p);        sum_r[i] = mo(sum_r[i - 1] + a[i] * mo(pos[n] - pos[i]) % p);    }        for(int i = 1;i <= n; ++ i)prefix_a[i] = mo(prefix_a[i - 1] + a[i]);        while(m --)    {        int x, l, r;scanf("%lld %lld %lld", &x, &l, &r);        int ans = 0;                if(l <= x and x <= r)ans = mo(f(x, l, x - 1) + f(x, x + 1, r));        else ans = f(x, l, r);                printf("%lld\n", ans);    }        return 0;}

糖糖别胡说，我真的不是签到题目

题目链接：https://ac.nowcoder.com/acm/problem/14583

本题有两种解法，第一种容易理解，第二种效率更优。

第一种解法：正向，multiset。

发功次数可以用一个桶来记录，让[1, i]的所有点的属性值都+1，相当于把后面的都-1，用一个fix表示偏移量。

建立两个multiset表示两组中的糖糖，好处是可以快速找出能力值最小的，从而去除掉。

扫一遍，把第i只糖糖加入到属于它的集合中，然后将另外一个集合中已有的能力值小的糖糖进行删除，再检查此时是否有发功。

最后集合中留下的糖糖个数即为答案。

#include #define int long longusing namespace std;const int maxn = 1e6 + 9, inf = 8e18;struct Node{int a, b;}p[maxn];int add[maxn];void solve(){int n, m;scanf("%lld %lld",&n, &m);    memset(add, 0, sizeof(int) * (n + 2));for(int i = 1;i <= n; ++ i)scanf("%lld %lld", &p[i].a, &p[i].b);    //注意同一时间可能施法多次for(int i = 1, x;i <= m; ++ i)scanf("%lld", &x), add[x] ++;    int fix = 0, cnt = 0;    multiset st[2];    for(int i = 1;i <= n; ++ i)    {        int a = p[i].a, b = p[i].b - fix;                st[a].insert(b);                while(!st[a ^ 1].empty() and *st[a ^ 1].begin() < b)            st[a ^ 1].erase(st[a ^ 1].begin()), cnt ++;                fix += add[i];}printf("%lld\n", n - cnt);}signed main(){int _;scanf("%lld", &_);while(_ --)solve();return 0;}

第二种解法：反向，思维。

我们想这么一个问题，一个糖糖x是否会被删除取决于在x出现之后，在另外一个集合中，是否出现了能力值高于x的能力值的糖糖y。

那么我们逆向遍历，维护两个集合的最值，当前的新加入的糖糖x的能力值如果低于另外一个集合中已经存在的（即右边的）糖糖能力值的最大值，说明他后面会被某个糖糖y删除掉，直接打上标记，但是我们不用真的删除。

糖糖x还可以用于删除左边的另一个集合的能力值较小的糖糖。注意此时的发功应该在循环开始时进行修改。

#include #define int long longusing namespace std;const int maxn = 1e6 + 9, inf = 8e18;struct Node{int a, b;}p[maxn];int add[maxn];void solve(){int n, m;scanf("%lld %lld",&n, &m);    memset(add, 0, sizeof(int) * (n + 2));for(int i = 1;i <= n; ++ i)scanf("%lld %lld", &p[i].a, &p[i].b);    //注意同一时间可能施法多次for(int i = 1, x;i = 1; -- i)    {        fix += add[i];        int a = p[i].a, b = p[i].b + fix;        mx[a] = max(mx[a], b);                if(mx[a ^ 1] > b)cnt ++;        }printf("%lld\n", n - cnt);}signed main(){int _;scanf("%lld", &_);while(_ --)solve();return 0;}

? 本文由eriktse原创，创作不易，如果对您有帮助，欢迎小伙伴们点赞?、收藏⭐、留言?