1 条题解

  • 0
    @ 2024-12-13 18:36:52
    #include<bits/stdc++.h>
    using namespace std;
    //本题利用二分答案 
    typedef long long int ll;
    ll n,c; 
    ll f(ll m)
    {
    	//t:要和那个点成为管理城市,t2:剩下  t3:算出基本花费 
    	ll t=(n-m)/(1ll*2*m),t2=(n-m)%(1ll*2*m),t3=(ll)2*m*t*(t+1)/2+(ll)(2*t+1)*(m-1)+(ll)m*c;
    	//如果剩下的比2小,就在t3上加上管理城市的费用
    	//否则还要加上路段建设 
    	if(t2<2)
    	{
    		return t3+(ll)t2*(t+1);
    	}else{
    		return t3+(ll)t2*(t+2)-2;
    	}
    }
    int main()
    {		
    	cin>>n>>c;
    	
    	ll l=1,r=n;
    	//特判如有一个点,则不需要钱 
    	if(n==1)
    	{
    		cout<<0;
    		exit(0); 
    	}
    	//二分答案求最小花费的城市 
    	while(l<r)
    	{
    		ll mid=(l+r)/2;
    		if(f(mid)<f(mid+1))
    		{
    			r=mid;
    		}else 
    		{
    			l=mid+1;
    		}
    	}
    	cout<<f(l);
    	return 0;
    }
    
    • 1

    信息

    ID
    2929
    时间
    1000ms
    内存
    512MiB
    难度
    10
    标签
    递交数
    62
    已通过
    2
    上传者