首页 > 其他分享 >题解 P11231【[CSP-S 2024] 决斗】

题解 P11231【[CSP-S 2024] 决斗】

时间:2024-11-04 19:10:01浏览次数:1  
标签:怪兽 游戏 int 题解 P11231 2024 leq 攻击 define

题目描述

今天是小 Q 的生日,他得到了 \(n\) 张卡牌作为礼物。这些卡牌属于火爆的“决斗怪兽”,其中,第 \(i\) 张卡代表一只攻击力为 \(r_i\),防御力也为 \(r_i\) 的怪兽。

一场游戏分为若干回合。每回合,小 Q 会选择某只怪兽 \(i\) 以及另一只怪兽 \(j(i \neq j)\),并让怪兽 \(i\) 向怪兽 \(j\) 发起攻击。此时,若怪兽 \(i\) 的攻击力小于等于怪兽 \(j\) 的防御力,则无事发生;否则,怪兽 \(j\) 的防御被打破,怪兽 \(j\) 退出游戏不再参与到剩下的游戏中。一只怪兽在整场游戏中至多只能发起一次攻击。当未退出游戏的怪兽都已发起过攻击时,游戏结束。

小 Q 希望决定一组攻击顺序,使得在游戏结束时,未退出游戏的怪兽数量尽可能少。

对于所有测试数据,保证:\(1 \leq n \leq 10^5\),\(1 \leq r_i \leq 10^5\)。

solution

可以优先将 \(r_i\) 小的怪物淘汰出局,也可以优先使用 \(r_i\) 小的怪物的攻击。对 \(r_i\) 排序后从小到大维护两个指针 \(i, j\),表示当前将要用 \(r_j\) 淘汰 \(r_i\),始终保持 \(r_j>r_i, j\leq n\),每次发动一次攻击后 \(i, j\) 都右移。复杂度 \(O(n\log n)\)。

code

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#define endl "\n"
#endif
using LL = long long;
int n, a[100010];
int main() {
#ifndef LOCAL
#ifdef NF
  freopen("duel.in", "r", stdin);
  freopen("duel.out", "w", stdout);
#endif
  cin.tie(nullptr)->sync_with_stdio(false);
#endif
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  sort(a + 1, a + n + 1);
  int ans = 0;
  for (int i = 1, j = 2; max(i, j) <= n; i++) {
    while (j <= n && a[j] <= a[i]) ++j;
    if (j <= n) ++ans, ++j;
  }
  cout << n - ans << endl;
  return 0;
}

标签:怪兽,游戏,int,题解,P11231,2024,leq,攻击,define
From: https://www.cnblogs.com/caijianhong/p/18526008/solution-P11231

相关文章

  • 题解 P11232【[CSP-S 2024] 超速检测】
    题目描述小D新入职了某国的交管部门,他的第一个任务是负责国家的一条长度为\(L\)的南北主干道的车辆超速检测。为了考考小D,上司首先需要他解决一个简化的场景。这个周末,主干道上预计出现\(n\)辆车,其中第\(i\)辆车从主干道上距离最南端\(d_i\)的位置驶入,以\(v_i\)的......
  • 题解 P11233【[CSP-S 2024] 染色】
    题目描述给定一个长度为\(n\)的正整数数组\(A\),其中所有数从左至右排成一排。你需要将\(A\)中的每个数染成红色或蓝色之一,然后按如下方式计算最终得分:设\(C\)为长度为\(n\)的整数数组,对于\(A\)中的每个数\(A_i\)(\(1\leqi\leqn\)):如果\(A_i\)左侧没有与其同......
  • 个人提升计划-2024
    今天的目标,就是定一个目标。打开博客,重新写学习计划。打开后台,一眼看到3年前定的学习计划,不禁有点好笑。3年前写的学习计划,终究是没有完成。时间如白驹过隙,转瞬即逝。3年就这么悄咪咪地过去了。收起诸多无用的感慨,制定好短期的个人提升计划吧。这个计划,我认为还是要先定好方向......
  • 牛客周赛 Round 66 题解
    牛客周赛Round66题解牛客周赛Round66A-小苯吃糖果_牛客周赛Round66#include<bits/stdc++.h>#defineendl'\n'usingnamespacestd;inta[5];voidsolve(){ for(inti=1;i<=3;i++)cin>>a[i]; sort(a+1,a+4); intans=max(a[1]+a[2],a[3]); cout<......
  • Codeforces Round 983 (Div. 2) 10.31 ABC题解
    CodeforcesRound983(Div.2)10.31题解A.Circuit数学(math)贪心(greedy)模拟(implementation)题意:有\(n\)盏灯,对应\(2\astn\)个开关,即每盏灯对应两个开关,开关打开或者关闭用\(1\)和\(0\)表示。给出\(2\astn\)个开关的状态,需要求解出可能开灯的最小数量和最大数量。......
  • 【网络云计算】2024第44周周考-解题思路
    文章目录1、网络类1.1、【网络类】arp的实操过程和总结1.2、IP地址的分类及地址范围1.3、网工/云计算SA必备网络故障排查思路和指令,不同维度分析,思路对应指令1.4、OSI和TCP模型,写成两列,并分别写出每层模型的含义2、架构类2.1、如何部署Tomcat,出错无法启动Tomcat实例,如何......
  • 【网络云计算】2024第45周小测第1次-Shell编程类
    文章目录1.1、CentOSStream9系统初始化的流程和步骤,步骤和指令对应,编写Shell脚本,并添加注释1.2、写出你所知道的所有的Shell编程的基本语法【网络云计算】2024第45周小测第1次-Shell编程类1.1、CentOSStream9系统初始化的流程和步骤,步骤和指令对应,编写Shell脚本......
  • 云原生周刊:微服务架构 2025 年的发展趋势 丨2024.11.4
    开源项目推荐KrakenDKrakenD是一个面向Kubernetes的API网关,专注于高性能和低延迟,旨在优化微服务之间的API调用。支持流量路由、负载均衡、速率限制和API聚合,极简配置。OctoDNSOctoDNS是一款为多云和混合云架构设计的DNS配置管理工具,支持多种DNS提供商,满足复杂环......
  • NeurIPS 2024 | 真实世界复杂任务,全新基准GTA助力大模型工具调用能力评测
     点击访问我的技术博客https://tmqcjr.com/利用语言模型调用工具,是实现通用目标智能体(general-purposeagents)的重要途径,对语言模型的工具调用能力提出了挑战。然而,现有的工具评测和真实世界场景存在很大差距,局限性主要体现在以下几个方面:评估问题通常是AI生成的,形式固......
  • NOIP2024模拟1
    rank6,T159,T250,T350,T40打了三道搜索。T4树套树没调出来就结束了香雪还没写,遗憾离场。玩游戏贪心,只会暴力跳……点此查看代码#include<bits/stdc++.h>usingnamespacestd;#definerep(i,s,t,p)for(inti=s;i<=t;i+=p)#definedrep(i,s,t,p)for(inti=s;i......