热门标签 | 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


推荐阅读
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • Explore how Matterverse is redefining the metaverse experience, creating immersive and meaningful virtual environments that foster genuine connections and economic opportunities. ... [详细]
  • 本文介绍如何在 Android 中通过代码模拟用户的点击和滑动操作,包括参数说明、事件生成及处理逻辑。详细解析了视图(View)对象、坐标偏移量以及不同类型的滑动方式。 ... [详细]
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • 技术分享:从动态网站提取站点密钥的解决方案
    本文探讨了如何从动态网站中提取站点密钥,特别是针对验证码(reCAPTCHA)的处理方法。通过结合Selenium和requests库,提供了详细的代码示例和优化建议。 ... [详细]
  • 火星商店问题:线段树分治与持久化Trie树的应用
    本题涉及编号为1至n的火星商店,每个商店有一个永久商品价值v。操作包括每天在指定商店增加一个新商品,以及查询某段时间内某些商店中所有商品(含永久商品)与给定密码值的最大异或结果。通过线段树分治和持久化Trie树来高效解决此问题。 ... [详细]
  • Java 中的 BigDecimal pow()方法,示例 ... [详细]
  • 本文深入探讨 MyBatis 中动态 SQL 的使用方法,包括 if/where、trim 自定义字符串截取规则、choose 分支选择、封装查询和修改条件的 where/set 标签、批量处理的 foreach 标签以及内置参数和 bind 的用法。 ... [详细]
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • Docker的安全基准
    nsitionalENhttp:www.w3.orgTRxhtml1DTDxhtml1-transitional.dtd ... [详细]
  • QUIC协议:快速UDP互联网连接
    QUIC(Quick UDP Internet Connections)是谷歌开发的一种旨在提高网络性能和安全性的传输层协议。它基于UDP,并结合了TLS级别的安全性,提供了更高效、更可靠的互联网通信方式。 ... [详细]
  • 本文介绍如何使用Objective-C结合dispatch库进行并发编程,以提高素数计数任务的效率。通过对比纯C代码与引入并发机制后的代码,展示dispatch库的强大功能。 ... [详细]
  • Java 中 Writer flush()方法,示例 ... [详细]
  • python的交互模式怎么输出名文汉字[python常见问题]
    在命令行模式下敲命令python,就看到类似如下的一堆文本输出,然后就进入到Python交互模式,它的提示符是>>>,此时我们可以使用print() ... [详细]
  • 本文详细介绍了如何在Linux系统上安装和配置Smokeping,以实现对网络链路质量的实时监控。通过详细的步骤和必要的依赖包安装,确保用户能够顺利完成部署并优化其网络性能监控。 ... [详细]
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社区 版权所有