首页 > 其他分享 >牛客小白月赛74 G 跳石头,搭tizi

牛客小白月赛74 G 跳石头,搭tizi

时间:2023-07-04 21:25:59浏览次数:51  
标签:Node tizi val int Sum long 牛客 74 Stack2

题目链接)

数据范围,2e5

区间越长越省力。

对于一个起点来说,从这里搭tizi最远到达的是序列中右侧第一个大于它的数所在的位置

用单调栈可以找到这样的区间,这些区间大致如下所示。

就是最多只会有包含的情况,但是不会出现交叉的情况。

然后可以这样渐次登高,到达最顶端。

下降的时候就是从末尾倒着再用一遍单调栈求出左侧第一个大于本身的数字所在位置

统计答案时可以选取可以减少体力最大的m个区间,

一个区间减少的体力为,没有体力的体力消耗-区间两端的山峰高度差。

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 2e5+10;
int n , m , top1 , top2 , tot;
int h[N] , Stack1[N] , Stack2[N];
long long Sum[N];
struct Node
{
	int l , r; long long val;
	Node(int l = 0 , int r = 0 , long long val = 0ll) : l(l) , r(r) , val(val) {}
	bool operator < (const Node &A) const { return val > A.val; }
}p[N];

inline int Abs(int x) { return x < 0 ? -x : x; }

int main()
{
    long long Answer = 0ll;
    scanf("%d%d" , &n , &m);
    for(int i = 1 ; i <= n ; ++i) scanf("%d" , &h[i]);
    for(int i = 2 ; i <= n ; ++i) Sum[i] = Sum[i-1] + Abs(h[i] - h[i-1]);
    top1 = top2 = 0;
    for(int i = 1 ; i <= n ; ++i)
    {
    	if(top1 == 0 || h[Stack1[top1]] <= h[i])
    		Stack1[++top1] = i;
    }
    for(int i = n ; i >= Stack1[top1] ; --i)
    {
    	if(top2 == 0 || h[Stack2[top2]] <= h[i])
    		Stack2[++top2] = i;
    }
    for(int i = 2 ; i <= top1 ; ++i)
    	p[++tot] = Node(Stack1[i - 1] , Stack1[i] , Sum[Stack1[i]] - Sum[Stack1[i-1]] - Abs(h[Stack1[i]] - h[Stack1[i-1]]));
    for(int i = top2 ; i >= 2 ; --i)
    	p[++tot] = Node(Stack2[i] , Stack2[i - 1] , Sum[Stack2[i-1]] - Sum[Stack2[i]] - Abs(h[Stack2[i]] - h[Stack2[i-1]]));
    sort(p + 1 , p + 1 + tot);
    Answer = Sum[n];
    for(int i = 1 ; i <= min(m , tot) ; ++i)
    	Answer -= p[i].val;
    printf("%lld\n" , Answer);
    return 0;
}

标签:Node,tizi,val,int,Sum,long,牛客,74,Stack2
From: https://www.cnblogs.com/sybs5968QAQ/p/17527039.html

相关文章

  • 牛客练习赛 112 B~C题题解
    卡B题了,难受B.qsggandSubarrayB-qsggandSubarray_牛客练习赛112(nowcoder.com)题意给定一个长为n的序列,求有多少个子区间的按位与和为0。思路要想按位与之和为0,那么对于区间的所有数,每个二进制位都要有一个0。设f[i]表示二进制位i的最右边一个0出现的位置,枚举序列的每......
  • (Leetcode)746
    //方式一:第一步不支付费用classSolution{publicintminCostClimbingStairs(int[]cost){intlen=cost.length;int[]dp=newint[len+1];//从下标为0或下标为1的台阶开始,因此支付费用为0dp[0]=0;dp[1]=0;......
  • 【leetcode】【1474】【删除链表 M 个节点之后的 N 个节点】
    c++第一个方法#include<algorithm>#include<iostream>#include<memory>#include<vector>//Definitionforsingly-linkedlist.structListNode{intval;ListNode*next;ListNode():val(0),next(nullptr){}Li......
  • 牛客小白月赛75
    D:给定01矩阵,规定0可以到1,1可以到0,将当前1变为0,将当前0变为1,花费都是1问从(1,1)走到(n,m)花费是多少,前提是移动都是相邻的点  考虑bfs,需要处理的是把当前点转化这个问题,其实可以分两种情况,对于相邻的点来说判断当前点和相邻点的点数是否相同而赋予两点之间的权值,不相邻的点也......
  • 牛客小白月赛75
    A.上班题意:分析:签到题代码:#include<bits/stdc++.h>usingnamespacestd;intmain(){intx,y,z;cin>>x>>y>>z;cout<<x+min(y,z);return0;}B.崇拜题意:分析:按知识点难度从大到小排序,然后计算按这个顺序讲解的最大崇......
  • 【题解】P8741 [蓝桥杯 2021 省 B] 填空问题 题解
    P8741[蓝桥杯2021省B]填空问题题解题目传送门欢迎大家指出错误并联系这个蒟蒻更新日志2023-05-0923:19文章完成2023-05-0923:20通过审核2023-06-2021:03优化了文章代码格式试题A:空间【解析】本题考察计算机存储的基础知识,只要掌握空间存储的换算方法,就能......
  • 【牛客小白75】D 矩阵 【bfs+优先队列】
    题目https://ac.nowcoder.com/acm/contest/60063/D题意是说,给你一张\(n*m(n,m\leq10^3)\)大小的01地图,当前点下一步只能走到相邻的点上,如果这两个点值相同,则代价为2,否则代价为1,问从(1,1)走到(n,m)最少代价是多少思路首先很容易想到只往右下走是错的,有可能往左和往上走总代价更......
  • 牛客小白月赛75
    C方豆子题意按照题意模拟,详见链接思路看到的第一眼就想递归,之后发现稍微有点麻烦没那么直接难度不高,模拟水题代码//>>>Qiansui#include<map>#include<set>#include<list>#include<stack>#include<cmath>#include<queue>#include<deque>#include<cstdio&g......
  • 一个基于STM32H743芯片和SOEM协议栈的EtherCAT主站源码。该源码提供了配套的CUBE工程,
    一个基于STM32H743芯片和SOEM协议栈的EtherCAT主站源码。该源码提供了配套的CUBE工程,使用的是SOEM协议栈的1.3.1版本。此外,还可以使用NUCLEO-H743ZI开发板进行配套开发。该系统支持DC同步,并且可以与多种驱动器型号配合使用,包括汇川IS620N、三洋RS3、赛孚德ASD620B、埃斯顿ProNet、......
  • 牛客图论 (第一章)
    F棋盘覆盖#include<bits/stdc++.h>usingnamespacestd;#definelllonglongconstintN=105,M=N*N*4,ID=N*N+N;intn,m;inthead[ID],ver[M],nxt[M],tot;boolban[N][N];intdx[]={1,-1,0,0},dy[]={0,0,1,-1};intmatch[ID];boolv[ID];......