2017 CCPC 秦皇岛 G 题 & ZOJ 3987 - Numbers (高精度+贪心)
发布日期:2021-06-29 14:25:23
浏览次数:2
分类:技术文章
本文共 1041 字,大约阅读时间需要 3 分钟。
题目大意
将一个数n拆分为m个数之和,求这m个数进行或操作后的最小值
题解
考虑贪心,我们知道,m个数的二进制中某一位有一个为 1 ,最终的结果这一位一定是 1,因此尽可能多的让这 m 个数充满二进制的这一位则为最优 记录 n 的二进制位数,从高位向低位开始枚举,对于当前位 i ,首先判断 n 是否可以充满 m 个 i 位以下的部分 若可以,则说明溢出部分会被放置在当前位,于是尽可能多的填充当前第 i 位共 m 个二进制位 若不可以,则说明剩余的数字可以被安置在低位,当前位为 0import java.math.BigInteger;import java.util.Scanner;public class Main { static BigInteger n,m; public static void solve() { int len=0; BigInteger tmp=n; len=tmp.bitLength(); BigInteger ans=BigInteger.valueOf(0); for(int i=len-1;i>=0&&n.compareTo(BigInteger.valueOf(0))>0;i--) { BigInteger cnt=BigInteger.ONE.shiftLeft(i); tmp=cnt.subtract(BigInteger.valueOf(1)).multiply(m);// 检验n是否可以填满m个低位 if(tmp.compareTo(n)<0) { // 若不可以填满则说明当前位一定被占用 n=n.subtract(cnt.multiply(m.min(n.shiftRight(i))));// 尽可能多的填充当前位 ans=ans.or(cnt); } } System.out.println(ans); } public static void main(String[] args) { Scanner cin=new Scanner(System.in); int t; t=cin.nextInt(); while(t-->0) { n=cin.nextBigInteger(); m=cin.nextBigInteger(); solve(); } }}
学如逆水行舟,不进则退
转载地址:https://chocolate.blog.csdn.net/article/details/100413130 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
初次前来,多多关照!
[***.217.46.12]2024年04月29日 14时58分39秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
JAVA 线程状态与优先级
2019-04-29
JAVA 守护线程 Deamon
2019-04-29
JAVA 简单实现TCP demo (2)
2019-04-29
JAVA 线程死锁
2019-04-29
JAVA Lock锁
2019-04-29
JAVA 线程同步机制 synchronized
2019-04-29
MySQL 安装教程(无脑版)
2019-04-29
JAVA 简单实现UDP demo
2019-04-29
MySQL 事务--转账
2019-04-29
JAVA UDP简单实现实时发送消息
2019-04-29
IDEA 怎么删除一个Module
2019-04-29
JAVA 和MySQL使用JDBC连接
2019-04-29
JAVA 反射的性能测试
2019-04-29
HTML 初探
2019-04-29
成功关键在于此:如何创造一个有即时价值的最小化可行产品?
2019-04-29
终端大改造:只需五步,构建你的梦中情“端”
2019-04-29
你的代码“balance”怎么样?找到简洁性和可读性的平衡点
2019-04-29
中科院刘康:低资源环境下的事件知识抽取
2019-04-29
提高软件工程技能的关键技术,这些资源赶紧收藏起来
2019-04-29
走进数据科学:最好是通过比网课更好的方法
2019-04-29