Codeforces Round #619 (Div. 2)C. Ayoub's function
比较好的题...
考虑一下正着来....十分复杂
不如考虑一下补集转换
有1=====全部-全0
考虑怎么可以把全0最小
发现全0最小时,0都是很小...(出现大的化一次增加很多)
于是保险一点,全0区间要尽可能的平均
于是就有了...答案
#include<bits/stdc++.h> using namespace std; int T; long long n,m,len,num1,num2,ans; int main(){ cin>>T; while(T--){ cin>>n>>m; len=(n-m)/(m+1); num1=(n-m-len*(m+1)); num2=m+1-num1; ans=n*(n-1)-len*(len+1)*num1-len*(len-1)*num2; ans/=2; cout<<ans+m<<endl; } }
我太菜了....