首页 > 代码库 > CodeForces 785C Anton and Fairy Tale
CodeForces 785C Anton and Fairy Tale
二分。
如果$n≤m$,显然只能$n$天。
如果$n>m$,至少可以$m$天,剩余还可以支撑多少天,可以二分计算得到,也可以推公式。二分计算的话可能爆$long$ $long$,上了个$Java$。
import java.math.BigInteger;import java.util.Scanner;public class Main { static Scanner cin = new Scanner(System.in); static BigInteger sum(BigInteger L,BigInteger R) { if(L.compareTo(R)>0) return BigInteger.ZERO; BigInteger A = L.add(R); BigInteger B = R.subtract(L); B = B.add(BigInteger.ONE); BigInteger c = A.multiply(B); return c.divide(BigInteger.valueOf(2)); } public static void main(String []args) { BigInteger m,n; n = cin.nextBigInteger(); m = cin.nextBigInteger(); if(n.compareTo(m)<=0) { System.out.println(n); } else { BigInteger ans = m; BigInteger sy = n.subtract(m); BigInteger hai = BigInteger.ZERO; BigInteger L = BigInteger.ZERO, R = sy; boolean pp=false; while(L.compareTo(R)<=0) { BigInteger mid = (L.add(R).divide(BigInteger.valueOf(2))); if(sum(ans.add(BigInteger.ONE),ans.add(mid)).compareTo(sy.add(m.multiply(mid)))<0) { pp=true; hai = mid; L = mid.add(BigInteger.ONE); } else if(sum(ans.add(BigInteger.ONE),ans.add(mid)).compareTo(sy.add(m.multiply(mid)))==0) { pp=false; hai = mid; L = mid.add(BigInteger.ONE); } else R = mid.subtract(BigInteger.ONE); } ans = ans.add(hai); if(pp == true) ans = ans.add(BigInteger.ONE); System.out.println(ans); } }}
CodeForces 785C Anton and Fairy Tale
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。