1 条题解
-
0大金狮 (mengqingyu) LV 10 @ 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
- 上传者