P4889 kls与flag

    • 981通过
    • 4.6K提交
  • 题目提供者 will7101 可爱
  • 评测方式 云端评测
  • 标签 排序 枚举,暴力 概率论,统计
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    kls毒奶非常厉害。

    题目描述

    有$n$个OI选手,每个人插了一个flag。有一天因为某种原因,flag都被触发了,所以地上有一排$n$根竹竿,竹竿的间距均为一个单位长度,高度在$1\sim m$之间。

    kls看到这些竹竿,感觉不好看,于是准备把它们全部放倒。

    在这之前,kls想到了一个数学问题。每根竹竿可以往左倒或者往右倒。如果两根竹竿在选择方向放倒之后,它们的顶端可以重合,那么称它们是优秀的。现在kls想要知道,有多少对竹竿是优秀的。

    输入输出格式

    输入格式:

    第一行两个数$n,m$,表示竹竿的个数和最大高度。

    第二行$n$个正整数,表示每根竹竿的高度。

    输出格式:

    输出一行,只有一个数,表示有多少对竹竿是优秀的。

    输入输出样例

    输入样例#1: 复制
    5 5
    2 3 3 3 2
    输出样例#1: 复制
    3

    说明

    样例解释

    法法

    • 1号和2号向左倒可以顶端重合
    • 4号和5号向右倒可以顶端重合
    • 1号向右,5号向左可以顶端重合

    数据范围

    对于30%的数据,满足$n\le 2000$,$m\le 5000$;

    对于60%的数据,满足$n\le 200000$,$m\le 500000$;

    对于100%的数据,满足$n \le 200000$,$m \le 10^9$。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。