题目描述
blablabla
emmmmmmm
分类讨论有点麻了
分三个情况吧
第一个是在环左边 中间 右边
在左边继续分 中点在哪
在中间直接二分哪个点直接往y走比x优
在右边直接差分即可
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
class Solution {
public:
vector<long long> countOfPairs(int n, int x, int y) {
if(x>y) swap(x,y);
vector<long long> d(n+10);
if(x==y){
for(int i=1;i<n;i++){
d[1]++;
d[n-i+1]--;
}
}else{
for(int i=1;i<n;i++)
{
if(i>=y)
{
d[1]++;
d[n-i+1]--;
}
else if(i<=x)
{
d[1]++;
d[x-i-1+1]--;
d[x-i+1+1]++;
d[x-i+1+n-y+1]--;
int now=y-x+1;
if(now==0) continue;
int c=x-1+(now+1)/2;
d[x-i]++;
d[x-i+c-x+1]--;
d[x-i+1]++;
d[x-i+1+y-(c+1)+1]--;
}
else//x+1到y-1
{
if(i!=y-1)
{
int l=i+1,r=y-1;
while(l<r){
int mid=(l+r+1)>>1;
if(mid-i<=i-x+1+y-mid) l=mid;
else r=mid-1;
}
d[1]++;
d[l-i+1]--;
d[i-x+1+1]++;
d[i-x+1+y-(l+1)+1]--;
}
//y-n都算了
int mn=min(i-x+1,y-i);
d[mn]++;
d[mn+n-y+1]--;
}
}
}
for(int i=1;i<=n;i++) d[i]+=d[i-1];
vector<long long > res;
for(int i=1;i<=n;i++){
res.push_back(d[i]*2);
}
return res;
}
};
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla