首页 > 其他分享 >题解:牛客多校第三场 A

题解:牛客多校第三场 A

时间:2024-07-24 16:39:35浏览次数:15  
标签:示例 int 题解 多校 walkers 步行者 第三场 Yes boat

A Bridging the Gap 2

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 1048576K,其他语言2097152K
Special Judge, 64bit IO Format: %lld

题目描述

A group of \(n\) walkers arrives at a riverbank at night. They want to cross the river using a boat, which is initially on their side. The boat can hold at most \(R\) walkers at a time and requires at least \(L (1≤L<R)\) walkers to operate.

Rowing the boat is a tiring task. Each time the boat is used to transport a group of walkers to the other side of the river, all walkers on the boat must have stamina greater than \(0\) , and each walker's stamina decreases by \(1\) after the trip. Initially, the \(i\)-th walker \((1≤i≤n)\) has a stamina value of \(h_i\).

You need to determine if it is possible to transport all the walkers to the other side of the river using the boat.

夜晚,一组 \(n\) 个步行者到达河岸。他们想使用一艘船过河,船最初在他们这边。这艘船一次最多可以载 \(R\) 个步行者,并且至少需要 \(L\)(\(1 \leq L < R\))个步行者来操作。

划船是一项累人的任务。每次使用船将一组步行者运送到河对岸时,船上的所有步行者的体力值都必须大于 \(0\),并且每次旅行后,每个步行者的体力值都会减少 \(1\)。最初,第 \(i\) 个步行者(\(1 \leq i \leq n\))的体力值为 \(h_i\)。

你需要判断是否有可能使用这艘船将所有步行者运送到河对岸。

输入描述:

The first line of input contains three integers \(n,L,R (1≤L<R≤n≤5×10^5 )\), denoting the number of walkers, the minimum and the maximum number of walkers to use the boat at a time, respectively.

The second line of input contains \(n\) integers \(h_1,h_2,\dots,h_n(1 \le h_i \le 5 \times 10^5)\) , where \(h_i(1≤i≤n)\) denotes the stamina value of the \(i\)-th walker.

第一行输入包含三个整数 \(n,L,R(1≤L<R≤n≤5×10^5 )\),分别表示步行者的数量、每次使用船只的最少步行者数量和最多步行者数量。

第二行输入包含 \(n\) 整数 \(h_1,h_2,\dots,h_n(1 \le h_i \le 5 \times 10^5)\) ,其中 \(h_i(1≤i≤n)\) 表示第 \(i\) 个步行者的体力值。

输出描述:

If it is possible to transport all the walkers to the other side of the river using the boat, output Yes in the first line (without quotes). Otherwise, output No in the first line (without quotes). You can output each letter in any case (lowercase or uppercase). For example, the strings yEs, yes, Yes, and YES will all be considered as positive replies.

如果可以用船将所有步行者运送到河对岸,则在第一行输出 Yes(不带引号)。否则,在第一行输出 No(不带引号)。您可以以任何大小写(小写或大写)输出每个字母。例如,字符串 yEs, yes, YesYES 都将被视为肯定回答。

示例1

输入

4 1 2
1 2 5 10

输出

Yes

示例2

输入

5 1 2
1 1 1 1 5

输出

No

示例3

输入

5 1 3
1 1 1 1 5

输出

Yes

示例4

输入

5 2 3
1 1 1 1 5

输出

No

示例5

输入

9 1 9
1 1 1 1 1 1 1 1 1

输出

Yes

题解

by Kylin & W.Sherlock.Henry

小船过河
过去一次每人需要消耗 \(1\) 点体力
来回一次就是 \(2\) 点

先预处理一下,每个人减去最后一次过去的耐力
剩下的耐力可用于来回运输

计算出总共最多可以来回多少次
再计算出每人最多可以来回多少次(不得大于总共的值)
这样可以有效防止溢出

给上述值求和,和 总共的次数与每次最少的人数的乘积 作比较
大于等于 就是能过
小于 就是不能过

我的代码

#include <iostream>
#include <algorithm>
#define int long long

int n,l,r,t;
const int N = 1e7 +10;
int a[N];
int need,sum;

signed main() {
    std::cin >> n >> l >> r;
    for(int i = 0 ; i < n ; i ++) {
        std::cin >> a[i];
        a[i] --;
    }

    t = (n-r)/(r-l) + ((n-r)%(r-l) ? 1 : 0);
    need = t*l;

    for(int i = 0 ; i < n ; i ++) {
        sum += std::min(a[i]/2,t);
    }

    if(sum < need) std::cout << "NO";
    else std::cout << "YES";
    return 0;
}

标签:示例,int,题解,多校,walkers,步行者,第三场,Yes,boat
From: https://www.cnblogs.com/jiejiejiang2004/p/18321150

相关文章

  • [题解]P3187 [HNOI2007] 最小矩形覆盖
    P3187[HNOI2007]最小矩形覆盖调了半天居然是因为没判断浮点精度误差才\(\colorbox{IndianRed}{\texttt{\color{White}{WA}}}\)了\(3\)个点,其他都没有问题!警钟长鸣……首先有一个结论:凸多边形的最小外接矩形一定和它的一条边重合。这个结论,网上几乎找不到完整的证明,目前发现......
  • [POI2012] PRE-Prefixuffix 题解
    前言题目链接:洛谷。题意简述给出长为\(n\)的串\(\texttt{S}\)。求最大的\(l\)满足:\[2l\leqn\land\texttt{S}[1\ldotsl]\doteq\texttt{S}[n-l+1\ldotsn]\]其中\(\doteq\)表示循环相同。题目分析看到循环相同,套路化想到,两个字符串一定可以表示成\(\tex......
  • 题解:2024牛客多校第三场 B
    BCrashTestheader时间限制:C/C++2秒,其他语言4秒空间限制:C/C++1048576K,其他语言2097152K64bitIOFormat:%lld题目描述Afterfiveyears,themosthigh-profileeventinmotorracing,Formula1,returnstoChina.TheChineseGrandPrixwasrecentlyheldatthe......
  • 题解:P10450 [USACO03MAR] Best Cow Fences G
    题目链接O(n^3)做法直接暴力枚举长度、起点,再全部跑一边求平均数。附上我丑陋的代码和提交记录,这个代码可以得42分。#include<bits/stdc++.h>usingnamespacestd;constintNR=1e5+5;longlongn,l,a[NR],sum,ave;intmain(){ cin>>n>>l; for(inti......
  • [CEOI2011] Matching 题解
    前言题目链接:洛谷。在上一题之后,模拟赛又放了一道KMP重定义相等的问题,但是寄了,故再记之。题意简述现在给出\(1\simn\)的排列\(p\)和序列\(h_1,h_2,\cdots,h_m\)​​,请你求出哪些\(h\)的子串符合排列\(p\)。串\(a_i\)符合一个排列被定义为其从小到大排序后得......
  • ABC250H 题解
    题面我们先考虑如何让连续的不在房子中的时间尽量短:我们考虑两个有房子的点\(x,y\),如果\(x\rightsquigarrowu\xrightarrow{w}v\rightsquigarrowy\)这条路径上除了\(x,y\)不存在有房子的点,那么我们可以找到这样一条路径,一定不劣:令\(a,b\)分别为最靠近\(u,v\)的有房......
  • 2024牛客多校3J Rigged Games
    欢迎来我的博客看这篇题解!Problem在两人竞技比赛中,对于任何正整数\(a\),我们定义\(BO(2a-1)\)如下:两名玩家继续竞争,直到其中一人获胜\(a\)次,那么他赢得整个比赛。\(BO(2a-1)\)最多包含\(2a-1\)小局游戏,最少包含\(a\)小局游戏。现在两个人进行一场DotA2比赛,使用的......
  • CF547D Mike and Fish 题解
    Description给定\(n\)个整点。你要给每个点染成红色或蓝色。要求同一水平线或垂直线上两种颜色的数量最多相差\(1\)。\(n,x_i,y_i\le2\times10^5\)。Solution考虑给每条水平线和垂直线建一个点,对于每个整点就把它对应的两条线连一条边。题目就转化为了给每条边定......
  • 2024牛客多校第三场
    磨合上升期,爽!B队友做的#include<bits/stdc++.h>usingnamespacestd;#defineintlonglonginlineintread(){intx=0;boolf=1;charch=getchar();for(;ch<'0'||ch>'9';ch=getchar())f^=(ch=='-');for(;ch>=&#......
  • ARC117F Gateau 题解
    ARC117FGateau题解题解区好像都没有对dp详细解释,本文将稍细致地说一说dp部分。题目大意给定一个长度为\(2N\)的环,环上每个节点有属性值\(B_i\(i=0,\dots,2N-1)\)和\(2N\)个限制,第\(i\)个限制形如\(\sum\limits_{j=i}^{i+N-1}B_j\geqA_i\),向环上的节点赋值,使得......