AtCoder Regular Contest 094 D Worst Case【思维题】

https://arc094.contest.atcoder.jp/tasks/arc094_b

题意：

　　在2次超多人的比赛中，你取得的成绩依次为第A名和第B名。一个人的成绩为a和b时，当且仅当ab<AB时，他会在综合排名中排在你前面。

　　显然同一次比赛的同一个名次只能被一个人拥有。

　　现在问综合排名排在你前面的最多有多少人？

题解：

这是官方答案：

想了好久，略有所悟>_<. 为便于叙述，令第一次比赛排名为a，第二次比赛排名为b。则必有a*b<A*B且a!=A,b!=B.

首先，考虑A=B的情况：

　　此时a=1到A-1 都能找到和他们相配的b，而且把a，b互换后答案也成立，所以此时有2*(A-1)种结果。而当a>A时，与其相配的数必然小于A,这样必然与前面的某个结果重复。所以ans=2*(A-1)

而当A、B相差1时，不妨令B=A+1：

　　同理a=1到A-1时也都能找到匹配的b，而当a=A+1时，b必然小于A，又会有和前面重复的情况。所以ans=2*(A-1)

在一般情况中，还令A<B：

　　令C为最大的C，满足C*C<A*B. 由于必然有A<=B<C,所以要去掉a=B的非法结果，所以a=1到C除了B都可以找到匹配的b。

　　对于a=C来说，若C*(C+1)<A*B ，那么a就可以取到C+1。，所以 ans=2*(C)-1。对于为什么a不能取到C+2，我是这么想的，既然找的C已经是最大的C满足C*C<A*B,那么必然会有(C+1)*(C+1)>=A*B。其实对于a可以取的最大值，对应的b一定是可以取值的最小值。如果a能取到C+2,那么必然能取到C+1,显然a=C+1最大只能和C配，那么C+2最大能和C-1配。好像没毛病？？我觉得这里我分析的有问题。。反例 A=2 B=7 不用取到C=4就有5种结果。。。。。。。。

　　否则a最多只能取到C，则有ans=2*(C-1)-1。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 
 5 int main() {
 6     int q;
 7     ll a, b;
 8     scanf("%d", &q);
 9     while (q--) {
10         scanf("%lld%lld", &a, &b);
11         if (a > b) swap(a, b);
12         ll ans=0;
13         ll c=a*b;
14         ll d=sqrt(c);
15         if(d*d==c) d--;
16         if(a==b||a==b+1)
17            ans=2*a-2;
18         else if(d*(d+1)>=a*b)
19             ans=2*d-2;
20         else ans=2*d-1;
21         cout<<ans<<endl;
22     }
23     return 0;
24 }