怎么没有二分的题解啊,写一篇。
题目链接
解题思路
发现我们可以将问题转化成将 \(n - m\) 个 \(1\) 分成 \(m\) 份,设第 \(i\) 份的数字之和为 \(sum_i\),则这样的分配方案的贡献为 \(\frac{n \times (n+1)}{2} - \sum_{i=1}^{n} sum_i^2\)。
容易发现要使得这样的贡献最小,你选择的不同的每份数字和的个数一定不超过 \(2\)。
因此你可以通过简单的数学来计算出这两种数字的取值,至于两种数字的数量可以直接二分。
单组测试时间复杂度 \(O(\log m)\)。
参考代码
#include<bits/stdc++.h>
using namespace std;
//#define map unordered_map
#define re register
#define ll long long
#define forl(i,a,b) for(re ll i=a;i<=b;i++)
#define forr(i,a,b) for(re ll i=a;i>=b;i--)
#define forll(i,a,b,c) for(re ll i=a;i<=b;i+=c)
#define forrr(i,a,b,c) for(re ll i=a;i>=b;i-=c)
#define pii pair<ll,ll>
#define mid ((l+r)>>1)
#define lowbit(x) (x&-x)
#define pb push_back
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
ll _t_;
void _clear(){}
ll n,m;
ll ans;
void solve()
{
ans=0;
_clear();
cin>>n>>m;
if(m==0)
{
cout<<0<<endl;
return ;
}
if(n==m)
{
cout<<(n+1)*n/2<<endl;
return ;
}
ll last=n-m;
ll num=last/(m+1);
// cout<<"number:"<<num<<endl;
ll L=0,R=m+1;
while(L<R)
{
ll Mid=(L+R+1)/2;
if(Mid*num<=last)
L=Mid;
else
R=Mid-1;
}
ll _0=L,_1=last-L*num;
_0-=_1;
// cout<<L<<":"<<_0<<' '<<_1<<endl;
cout<<(n+1)*n/2 - (_0*(num+1)*num/2 + _1*(num+2)*(num+1)/2)<<endl;
}
int main()
{
IOS;
_t_=1;
cin>>_t_;
while(_t_--)
solve();
QwQ;
}
标签:数字,ll,re,杂题,sum,CF1301C,define
From: https://www.cnblogs.com/wangmarui/p/18400804