热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

BZOJ1034详细解析与算法优化

本文深入解析了BZOJ1034问题,并提出了优化算法。通过借鉴广义田忌赛马的贪心策略,当己方当前最弱的马优于对方最弱的马时进行匹配;同样地,若己方当前最强的马优于对方最强的马,也进行匹配。此方法在保证胜率的同时,有效提升了算法效率。

【解题思路】

  广义田忌赛马的贪心模型。如果当前实力最差的马比对手实力最差的马强,则匹配;如果当前实力最强的马比对手实力最强的马强,亦匹配;若上述两点均不成立,拿己方最差的马去匹配对手最强的马。复杂度O(nlog2n)。

【参考代码】

1 #include
2 #include
3 #define REP(i,low,high) for(register int i&#61;(low);i<&#61;(high);&#43;&#43;i)
4 #define __function__(type) __attribute__((optimize("-O2"))) inline type
5 #define __procedure__ __attribute__((optimize("-O2"))) inline void
6 using namespace std;
7
8 __function__(int) score(const int&x,const int&y) {return x&#61;&#61;y?1:(x>y)*2;}
9
10 static int n; int a[100010],b[100010];
11
12 int main()
13 {
14 scanf("%d",&n); REP(i,1,n) scanf("%d",a&#43;i); REP(i,1,n) scanf("%d",b&#43;i);
15 sort(a&#43;1,a&#43;n&#43;1),sort(b&#43;1,b&#43;n&#43;1); int la&#61;1,ra&#61;n,lb&#61;1,rb&#61;n,ans&#61;0;
16 while(la<&#61;ra)
17 {
18 if(a[la]>b[lb]) {ans&#43;&#61;score(a[la&#43;&#43;],b[lb&#43;&#43;]); continue;}
19 if(a[ra]>b[rb]) {ans&#43;&#61;score(a[ra--],b[rb--]); continue;}
20 ans&#43;&#61;score(a[la&#43;&#43;],b[rb--]);
21 }
22 printf("%d ",ans),la&#61;1,ra&#61;n,lb&#61;1,rb&#61;n,ans&#61;0;
23 while(la<&#61;ra)
24 {
25 if(a[la]continue;}
26 if(a[ra]continue;}
27 ans&#43;&#61;score(a[ra--],b[lb&#43;&#43;]);
28 }
29 return printf("%d\n",ans),0;
30 }

View Code

 


转载于:https://www.cnblogs.com/spactim/p/6538937.html


推荐阅读
  • Explore how Matterverse is redefining the metaverse experience, creating immersive and meaningful virtual environments that foster genuine connections and economic opportunities. ... [详细]
  • Java 中的 BigDecimal pow()方法,示例 ... [详细]
  • 使用 Azure Service Principal 和 Microsoft Graph API 获取 AAD 用户列表
    本文介绍了一段通用代码示例,该代码不仅能够操作 Azure Active Directory (AAD),还可以通过 Azure Service Principal 的授权访问和管理 Azure 订阅资源。Azure 的架构可以分为两个层级:AAD 和 Subscription。 ... [详细]
  • 本文探讨了如何在模运算下高效计算组合数C(n, m),并详细介绍了乘法逆元的应用。通过扩展欧几里得算法求解乘法逆元,从而实现除法取余的计算。 ... [详细]
  • 本文详细介绍了Java中的访问器(getter)和修改器(setter),探讨了它们在保护数据完整性、增强代码可维护性方面的重要作用。通过具体示例,展示了如何正确使用这些方法来控制类属性的访问和更新。 ... [详细]
  • MySQL索引详解与优化
    本文深入探讨了MySQL中的索引机制,包括索引的基本概念、优势与劣势、分类及其实现原理,并详细介绍了索引的使用场景和优化技巧。通过具体示例,帮助读者更好地理解和应用索引以提升数据库性能。 ... [详细]
  • 本文探讨了在通过 API 端点调用时,使用猫鼬(Mongoose)的 findOne 方法总是返回 null 的问题,并提供了详细的解决方案和建议。 ... [详细]
  • golang常用库:配置文件解析库/管理工具viper使用
    golang常用库:配置文件解析库管理工具-viper使用-一、viper简介viper配置管理解析库,是由大神SteveFrancia开发,他在google领导着golang的 ... [详细]
  • 本文介绍如何在 Android 中通过代码模拟用户的点击和滑动操作,包括参数说明、事件生成及处理逻辑。详细解析了视图(View)对象、坐标偏移量以及不同类型的滑动方式。 ... [详细]
  • 1:有如下一段程序:packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]
  • 本文详细介绍了如何构建一个高效的UI管理系统,集中处理UI页面的打开、关闭、层级管理和页面跳转等问题。通过UIManager统一管理外部切换逻辑,实现功能逻辑分散化和代码复用,支持多人协作开发。 ... [详细]
  • 本文探讨了 Objective-C 中的一些重要语法特性,包括 goto 语句、块(block)的使用、访问修饰符以及属性管理等。通过实例代码和详细解释,帮助开发者更好地理解和应用这些特性。 ... [详细]
  • 本文详细介绍了 Apache Jena 库中的 Txn.executeWrite 方法,通过多个实际代码示例展示了其在不同场景下的应用,帮助开发者更好地理解和使用该方法。 ... [详细]
  • 题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!-----&# ... [详细]
  • 本文探讨了《魔兽世界》中红蓝两方阵营在备战阶段的策略与实现方法,通过代码展示了双方如何根据资源和兵种特性进行战士生产。 ... [详细]
author-avatar
lilin
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有