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); } }
}
上一篇:在Eclipse中用SWT设计界面


下一篇:Hadoop-1.2.1学习之Job创建和提交源码分析