自动搬运

查看原文

来自洛谷，原作者为

	LuoXH Something wrong...

搬运于2025-08-24 23:08:21，当前版本为作者最后更新于2025-01-10 20:38:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目。

题目中说“比赛结果中任何两个玩家的得分之比最多为 $k$”，我们假设三个玩家的得分分别为 $a,b,c$，且 $a\leq b\leq c$，因而由题意及我们刚刚设的内容得：$a\leq b \leq ak$，和 $a\leq c \leq ak$，则 $\dfrac{c}{b} \leq k$

(若 $\dfrac{c}{b}=t>k$，则 $c=bt>bk$，因为 $a\leq b$，所以 $ak\leq bk$，又所以 $ak<bt$，得 $ak<c$，与 $c\leq ak$ 矛盾，因此 $t\leq k$)

那么由此我们可以想到一种方法：枚举 $a$，再计算 $b,c$ 的个数以及三人比分的方案数。

$a$ 可以暴力枚举，而对于 $b,c$ 的取值方案数以及比分方案数，由于 $b,c$ 范围确定，可以计算得到（我用的方法是将卡片进行排序，再将相同的合并，再二分搜索找出 $b,c$ 的取值范围，用乘法原理进行计算。注意：可能需要将 $b,c$ 都不等于 $a$，$b$ 或 $c$ 之一等于 $a$，$b$ 和 $c$ 都等于 $a$ 进行分类讨论）

时间复杂度 $O(n\log n)$。

代码如下：（写得比较丑，勿喷）（注意：由于$k,x_i\leq 10^9$，因此要开 long long。否则有分，但不多。）

#include<bits/stdc++.h>
using namespace std;
long long a[100005],n,k,b[100005],c[100005],cnt,su[100005];
int main(){
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		if(a[i]!=a[i-1]){
			cnt++;
			b[cnt]=a[i];
			c[cnt]=1;
			su[cnt]=su[cnt-1];
		}
		else{
			c[cnt]++;
			if(c[cnt]==2) su[cnt]++;
		}
	}
	long long ans=0;
	for(int i=1;i<=cnt;i++){
		long long l=i,r=cnt,g=i;
		while(l<=r){
			long long mid=l+r>>1;
			if(b[mid]<=b[i]*k){
				g=mid;
				l=mid+1;
			}
			else{
				r=mid-1;
			}
		}
		if(g==i){
			if(c[i]>=3){
				ans++;
			}
			continue;
		}
		ans+=(g-i)*(g-i-1)*3;
		ans+=(su[g]-su[i])*3;
		if(c[i]>=2){
			ans+=3*(g-i);
		}
		if(c[i]>=3){
			ans++;
		}
	}
	printf("%lld\n",ans);
	return 0;
}