首页 > 其他分享 >LOJ4218 「IOI2024」尼罗河船运 题解

LOJ4218 「IOI2024」尼罗河船运 题解

时间:2024-09-08 17:13:24浏览次数:12  
标签:le 下标 int 题解 maxn IOI2024 vi LOJ4218 define

题目描述

有 \(n\) 件手工艺品,第 \(i\) 件重量为 \(w_i\) ,有参数 \(a_i\) 和 \(b_i\) 。

每艘船最多可以运输两件手工艺品:

  • 如果只运输第 \(i\) 件,重量没有要求,代价为 \(a_i\) 。
  • 如果同时运输第 \(i\) 和第 \(j\) 件,要求 \(|w_i-w_j|\le D\) ,代价 \(b_i+b_j\) 。

\(q\) 次询问,给定 \(D\) ,求运输所有物品的最小总代价。

数据范围

  • \(1\le n,q\le 10^5\) 。
  • \(1\le b_i\lt a_i\le 10^9,1\le w_i,D\le 10^9\) 。

时间限制 \(\texttt{2s}\) ,空间限制 \(\texttt{2048MB}\) 。

分析

令初始代价为 \(\sum_{i=1}^n a_i\) ,则第 \(i\) 件商品合运可以节约 \(c_i=a_i-b_i\) 的代价。

将所有商品按 \(w_i\) 排序,假设合运的下标集合为 \(s_1,\cdots,s_{2k}\) ,显然让 \(s_1\) 与 \(s_2\) 合运,\(\cdots\) , \(s_{2k-1}\) 与 \(s_{2k}\) 合运最优。

\(f_i\) 表示仅考虑前 \(i\) 件商品,最多能节约的代价。转移方程为:

\[f_i=\max(f_{i-1},\max_{w_j\ge w_i-D}f_{j-1}+c_j+c_i)\\ \]

合法的 \(j\) 是一段后缀,单调队列维护 \(f_{j-1}+c_j\) 的最大值即可做到 \(\mathcal O(qn)\) ,可以通过前 \(5\) 个子任务。

观察子任务 \(6\) ,此时 \(c_i\) 全为 \(1\) 。按照 \(D\) 升序扫描所有询问,将相邻重量差 \(\le D\) 的位置连起来,则答案为 \(\sum\lfloor\) 连续段长度 \(/2\rfloor\) 。

对于一般情况,如果连续段长度为偶数,那么我们全盘保留;如果连续段长度为奇数,那么我们丢且仅丢一个商品。

容易发现丢商品的限制与下标奇偶性有关,比如说,假设连续段开头下标为奇数,那么下标为奇数的商品可以无条件丢弃(左右都是偶数个商品,刚好完成配对),但下标为偶数的商品要求 \(w_{i+1}-w_{i-1}\le D\) 才能丢弃(因为第 \(i-1\) 和第 \(i+1\) 个商品会配对)。

在扫描 \(D\) 的过程中,对连续段内奇偶下标分别维护 \(c_i\) 最小值和满足 \(w_{i+1}-w_{i-1}\le D\) 的 \(c_i\) 最小值,动态更新答案即可。

由于只会进行 \(\mathcal O(n)\) 次连续段合并,所以时间复杂度 \(\mathcal O(n+q)\) 。

#include<bits/stdc++.h>
#include"nile.h"
#define ll long long
#define vi vector<int>
#define fi first
#define se second
#define mp make_pair
#define pii pair<int,int>
using namespace std;
const int maxn=1e5+5,inf=1e9+5;
int f[maxn],w[maxn];
pii d[maxn],p[maxn],r[maxn],s[maxn];
struct node
{
    int len,val;
    int mn[2][2]={inf,inf,inf,inf};
    void calc(int x)
    {
        val=len&1?min(mn[x][0],mn[x^1][1]):0;
    }
}o[maxn];
int find(int x)
{
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}
void chmin(int &x,int y)
{
    if(x>=y) x=y;
}
vector<ll> calculate_costs(vi w,vi a,vi b,vi e)
{
    int n=w.size(),q=e.size();
    ll res=0;
    for(int i=0;i<n;i++) p[i]=mp(w[i],a[i]-b[i]),res+=a[i];
    for(int i=0;i<q;i++) d[i]=mp(e[i],i);
    sort(p,p+n),sort(d,d+q);
    for(int i=0;i<n;i++) f[i]=i,w[i]=p[i].fi,o[i].len=1,o[i].mn[i&1][0]=o[i].val=p[i].se;
    for(int i=0;i<n;i++) r[i]=mp(i?w[i]-w[i-1]:inf,i),s[i]=mp(i&&i!=n-1?w[i+1]-w[i-1]:inf,i);
    sort(r,r+n),sort(s,s+n);
    vector<ll> vec(q);
    for(int i=0,j=0,k=0;i<q;i++)
    {
        while(j<n&&r[j].fi<=d[i].fi)
        {
            int v=r[j].se,u=find(v-1);
            res-=o[u].val+o[v].val,f[v]=u,o[u].len+=o[v].len;
            for(int x=0;x<=1;x++)
                for(int y=0;y<=1;y++)
                    chmin(o[u].mn[x][y],o[v].mn[x][y]);
            o[u].calc(u&1),res+=o[u].val,j++;
        }
        while(k<n&&s[k].fi<=d[i].fi)
        {
            int v=s[k].se,u=find(v);
            res-=o[u].val;
            chmin(o[u].mn[v&1][1],p[v].se);
            o[u].calc(u&1),res+=o[u].val,k++;
        }
        vec[d[i].se]=res;
    }
    return vec;
}

标签:le,下标,int,题解,maxn,IOI2024,vi,LOJ4218,define
From: https://www.cnblogs.com/peiwenjun/p/18403147

相关文章

  • Leetcode第 414 场周赛题解
    Leetcode第414场周赛题解Q1.将日期转换为二进制表示给你一个字符串date,它的格式为yyyy-mm-dd,表示一个公历日期。date可以重写为二进制表示,只需要将年、月、日分别转换为对应的二进制表示(不带前导零)并遵循year-month-day的格式。返回date的二进制表示。解法:STL一......
  • 题解:P11020 「LAOI-6」Radiation
    我们发现一种最优策略,把石头按照斜线摆,即(1,1),......
  • P1419 寻找段落 题解
    其他学习笔记这题真是凝聚了很多精华,那么我们就介绍这题的四兄弟:大哥平均数这道题是其他兄弟的基础。二哥BestCow这位更是重量级,因为没特长只能强大哥的外貌,会大哥即识二哥。三哥PROSJEK这位哥看似有点创新却仍没逃过一家子的基因,只是变为了小数运算。四哥寻......
  • 【题解】CPS-S模拟2
    目录PreT1.不相邻集合题目描述部分分40pts10pts正解思路代码T2.线段树题目描述部分分20pts正解思路代码T3.部分分40pts正解思路代码T4.部分分10pts正解思路代码AndPre赛时没有第一时间找到签到题,遂四处游走,后来决定先打T1,约1h时切了,然后1h打后3题暴力,后面推了推T4一个特殊性质,......
  • [ABC370C] Word Ladder 题解
    题目描述:给予两个相等长度的序列,\(S\)与\(T\),以及一个空数组\(X\),每在\(S\)上修改一个字符,便将修改后的\(S\)加入\(X\)中,直到\(S\)与\(T\)相同。(输出字典序最小的\(X\)数组)拿过题一看,感觉还是蛮简单的,本题主要的难点在字符串的字典序上。字符串字典序的定义......
  • P11019 「LAOI-6」[太阳]] 请使用最新版手机 QQ 体验新功能 题解
    非常简单的模拟题。由题意得,即找出输入字符串中,用[]围起来的片段中的大写字母\(A_1,A_2,A_3...A_n\)然后将其转换为小写输出\(/a_1a_2a_3...a_n\)即可。#include<bits/stdc++.h>#defineseq(q,w,e)for(intq=w;q<=e;q++)#definelllonglongusingnamespace......
  • P11020 「LAOI-6」Radiation 题解
    一道简单的构造题,其实不用想的十分复杂的说。首先,最多发射的宇宙射线\(sum\)也最多为\(sum_{max}=min(m,n)\)也就是说,无论如何摆放石子,也只能达到这个数量。那么我们的目的便变成了如何让石子变成这一个形状。如上图,在一个\(3\times6\)的矩阵中,其实只要三颗石子即可满足......
  • AtCoder Beginner Contest 370 A-F题解
    A#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;mt19937rnd(time(0));#defineintlonglongtypedeftuple<int,int,int>tp;#definexfirst#defineysecondtypedefpair<int,int>pii;typedefpair<double,double>......
  • 配置PHP的Session存储到Mysql / Redis / memcache 以及使用opcache以及apc缓存清除工
    一、配置PHP的Session存储到Mysql,Redis以及memcache等        PHP的会话默认是以文件的形式存在的,可以通过简单的配置到将Session存储到NoSQL中,即提高了访问速度,又能很好地实现会话共享!1.默认配置:session.save_handler=filessession.save_path=/tmp/2.配......
  • 【洛谷 P1996】约瑟夫问题 题解(队列+模拟+循环)
    约瑟夫问题题目描述个人围成一圈,从第一个人开始报数,数到的人出列,再由下一个人重新从开始报数,数到的人再出圈,依次类推,直到所有的人都出圈,请输出依次出圈人的编号。注意:本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰名小朋友,而该题是全部出圈。输入......