简要题意:略。
考虑一个位置的最大不满意度,就是在 (t) 的时间内,有 (lfloor frac{t}{x} floor) 个选手间隔 (x) 时间开始比赛,于是其不满意度为 (lfloor frac{t}{x} floor). 不妨设 ( ext{mid} = lfloor frac{t}{x} floor)
这个不满意度取不到的时候,你会发现选手数量不够了。因此易得答案的贡献值长这样:
( ext{mid}, ext{mid}, ext{mid} cdots ext{mid}, ext{mid}-1, ext{mid}-2 cdots 0)
于是考虑中间选手的位置。很明显是 (n- ext{mid}).
两边求和。注意特判 (n< ext{mid}) 的情况。
时间复杂度:(mathcal{O}(T)).
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ld long double
inline ll read(){char ch=getchar(); int f=1; while(!isdigit(ch)) {if(ch=='-') f=-f; ch=getchar();}
ll x=0;while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); return x*f;}
int T; ll n,x,t;
int main() {
T=read(); while(T--) {
n=read(),x=read(),t=read();
ll mid=t/x;
if(n<mid) {printf("%lld
",n*(n-1)/2); continue;}
ll lft=(n-mid)*mid; //左边可以取到 mid 的答案
ll rht=(mid-1)*mid/2; //右边等差数列求和
printf("%lld
",lft+rht);
}
return 0;
}