MT3032 环形喂猪

简介: MT3032 环形喂猪

93d3f654e08049a78126ee51bdd95a9f.jpg

792379819cc142c68a8ab20d005aa5ae.jpg

思路:

1.输出Error的情况:m>n/2

2.首先将饥饿值放到大根堆中,先喂最饿的猪i,则把i的饥饿值加到sum中;但也又可能喂i-1和i+1,所以此时需要反悔:把i取出来的同时,将a[i-1]+a[i+1]-a[i]放入堆中。(即保留取i,也保留取i-1和i+1的可能性),此时将i-1,i,i+1合并为一个节点

#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 10;
int n, m, l[N], r[N], ans, a[N], tot;
bool mark[N];
struct node
{
    int id, v; // v为饥饿值
    bool operator<(const node &a) const
    { // 使用大根堆,重载<号
        return v < a.v;
    }
} tmp;
priority_queue<node> q; // 大根堆
int main()
{
    cin >> n >> m;
    if (m > n / 2)
    {
        cout << "Error!";
        return 0;
    }
 
    else
    {
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        for (int i = 2; i < n; i++)
        { // 处理链表
            l[i] = i - 1, r[i] = i + 1;
            q.push({i, a[i]});
        }
        // 处理环形(使用链表存储)
        l[1] = n, r[1] = 2;
        l[n] = n - 1, r[n] = 1;
        q.push({1, a[1]});
        q.push({n, a[n]});
        tot = n;
        for (int i = 1; i <= m; i++)
        {
            tmp = q.top(); // 取出堆头节点放入tmp中
            q.pop();
            if (mark[tmp.id])
            { // 如果已经被标记,即若取i,则标记i-1和i+1表示不能被取
                i--;
                continue;
            }
            ans += tmp.v; // 没被标记,则加到答案中
            // 新增节点
            a[++tot] = a[l[tmp.id]] + a[r[tmp.id]] - a[tmp.id];
            q.push({tot, a[tot]}); // 合并成一个节点
            // 更新链表中左右指针位置关系
            // 因为取了i就不能取i-1和i+1,所以位置关系类似
            //  i-2 tot i+2    tot为i-1 i i+1  tmp为i
            l[tot] = l[l[tmp.id]]; // tot左边为i-2,即tmp的l的l
            r[l[l[tmp.id]]] = tot; // i-2的右边为tot
            r[tot] = r[r[tmp.id]]; // tot右边为i+2,即tmp的r的r
            l[r[r[tmp.id]]] = tot; // i+2的左边为tot
            // 将这三个节点标记为已被处理
            mark[tmp.id] = mark[l[tmp.id]] = mark[r[tmp.id]] = 1;
        }
        cout << ans;
        return 0;
    }
}


相关文章
|
JSON Java API
探秘JDK 13的黑科技:新特性一览
探秘JDK 13的黑科技:新特性一览
234 0
|
Docker 容器
尝试添加 --skip-broken 来跳过无法安装的软件包 或 --nobest 来不只使用最佳选择的软件包
尝试添加 --skip-broken 来跳过无法安装的软件包 或 --nobest 来不只使用最佳选择的软件包
1844 0
尝试添加 --skip-broken 来跳过无法安装的软件包 或 --nobest 来不只使用最佳选择的软件包
|
7月前
|
图形学 开发者
Unity中的透明效果之开启深度写入半透明效果
在Unity中实现开启深度写入的半透明效果,通过分离渲染过程为两个阶段:深度写入和颜色混合。首先,在深度写入阶段仅写入深度信息而不渲染颜色;其次,在颜色混合阶段进行正常的半透明颜色混合,确保后续物体能正确渲染且避免被错误裁剪。该方法解决了常规半透明渲染中关闭深度写入导致的问题。提供自定义Shader代码及材质设置步骤,方便开发者实现这一特殊渲染需求。
|
11月前
|
存储 算法 Java
数据结构与算法学习八:前缀(波兰)表达式、中缀表达式、后缀(逆波兰)表达式的学习,中缀转后缀的两个方法,逆波兰计算器的实现
前缀(波兰)表达式、中缀表达式和后缀(逆波兰)表达式的基本概念、计算机求值方法,以及如何将中缀表达式转换为后缀表达式,并提供了相应的Java代码实现和测试结果。
1166 0
数据结构与算法学习八:前缀(波兰)表达式、中缀表达式、后缀(逆波兰)表达式的学习,中缀转后缀的两个方法,逆波兰计算器的实现
|
人工智能 测试技术 开发者
大模型自动生成并运行代码的体验与优化
随着近两年大模型的不断发展,它们在各个领域展示出了惊人的能力,可以说是在各个领域到了“开花结果”的阶段。比如最近技术圈比较火的阿里云的通义千问已经可以自己写代码、跑代码了,作为开发者,我觉得这种能力不仅提高了开发效率,还推动了编程实践向更高层次的转变和发展。但是,在使用大模型自动生成代码时,我们也会面临一些挑战,其中之一是代码可能会曲解开发者的需求。那么本文就来分享一下个个人的体验以及如何优化这种情况。
1228 2
大模型自动生成并运行代码的体验与优化
|
11月前
|
SQL 分布式计算 关系型数据库
Hadoop-22 Sqoop 数据MySQL到HDFS(全量) SQL生成数据 HDFS集群 Sqoop import jdbc ETL MapReduce
Hadoop-22 Sqoop 数据MySQL到HDFS(全量) SQL生成数据 HDFS集群 Sqoop import jdbc ETL MapReduce
186 0
|
机器学习/深度学习 人工智能 安全
人工智能在网络安全中的入侵检测与防御
人工智能在网络安全中的入侵检测与防御
|
机器学习/深度学习 计算机视觉
【YOLOv8改进-论文笔记】RFAConv:感受野注意力卷积,创新空间注意力
【YOLO目标检测专栏】探索空间注意力局限,提出感受野注意力(RFA)机制,解决卷积核参数共享问题。RFAConv增强大尺寸卷积核处理能力,不增加计算成本,提升网络性能。已在YOLOv8中实现,详情见YOLO目标检测创新改进与实战案例专栏。
|
芯片
数电实验 数字电子钟设计 基于quartus 实现计时校时闹钟秒表稍复杂音频 分享电路图设计以及工程文件
数电实验 数字电子钟设计 基于quartus 实现计时校时闹钟秒表稍复杂音频 分享电路图设计以及工程文件
2443 3
数电实验 数字电子钟设计 基于quartus 实现计时校时闹钟秒表稍复杂音频 分享电路图设计以及工程文件
|
Java 编译器 API
4.3 Lambda表达式的性能与限制:在某些情况下避免使用Lambda表达
4.3 Lambda表达式的性能与限制:在某些情况下避免使用Lambda表达
2168 0