Rikka with Time Complexity
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 448 Accepted Submission(s): 159
Problem Description
Calculating and comparing time complexity for algorithms are the most important necessary skills for CS students.
This semester, Rikka applies for the assistant of course "Algorithm Analysis". Now Rikka needs to set problems for the final examination, and she is going to set some tasks about time complexity.
Let fa(n)=log…logn (there are exactly a log in this function, and log uses base 2). And then, for an integer array A, Rikka defines gA(n) in the following way (B is the suffix of A with length |A|−1):
For example, g[1,2](n)=(logn)loglogn and g[3,1,1](n)=(logloglogn)(logn)logn.
Now, given integer arrays A and B, Rikka wants you to compare gA(n) with gB(n). i.e., let k be limn→+∞gA(n)gB(n). If k=0, output −1; if k=+∞, output 1; otherwise output 0.
This semester, Rikka applies for the assistant of course "Algorithm Analysis". Now Rikka needs to set problems for the final examination, and she is going to set some tasks about time complexity.
Let fa(n)=log…logn (there are exactly a log in this function, and log uses base 2). And then, for an integer array A, Rikka defines gA(n) in the following way (B is the suffix of A with length |A|−1):
gA(n)={fA1(n)fA1(n)gB(n)|A|=1|A|>1
For example, g[1,2](n)=(logn)loglogn and g[3,1,1](n)=(logloglogn)(logn)logn.
Now, given integer arrays A and B, Rikka wants you to compare gA(n) with gB(n). i.e., let k be limn→+∞gA(n)gB(n). If k=0, output −1; if k=+∞, output 1; otherwise output 0.
Input
The first line contains a single number t(1≤t≤105), the number of testcases.
For each testcase, the first line contains two integers a,b(1≤a,b≤3), the length of A and B.
The second line contains a integers Ai and the third line contains b integers Bi(1≤Ai,Bi≤109), which describe A and B.
For each testcase, the first line contains two integers a,b(1≤a,b≤3), the length of A and B.
The second line contains a integers Ai and the third line contains b integers Bi(1≤Ai,Bi≤109), which describe A and B.
Output
For each testcase, output a single line with a single integer, the answer.
Sample Input
3
1 1
1
2
2 2
1 2
2 1
1 3
1
1000000000 3 3
Sample Output
1
-1
-1
题意：定义 f(a) = loglog...log(n) (有a个log)，g(A) = f(a1)^f(a2)^f(a3)，求lim(n->+∞)g(A)/g(B)
分析：
考虑A数组最多有三个数，所以对g(A)取两次log
即：loglog(f(a1)^f(a2)^f(a3)) = log(f(a2)^f(a3)*log(f(a1)) = log(f(a2)^f(a3)) + loglog(f(a1)) = f(a3)*log(f(a2) + loglog(f(a1)) = f(a3)*f(a2+1) + f(a1+2)
将上式去掉log和极限后可化为：a3*(a2+1)+(a1+2)*inf（因为n->+∞，去掉log后(a1+2)还要乘上一个inf，(log)inf n n->inf等于1）
注意a1,a2,a3越大，f(a1),f(a2),f(a3)的值越小，所以去掉log后上下式子比较大小得到的结果是相反的
即：lim(n->+∞)g(A)/g(B) = lim(n->+∞)((a3*(a2+1)+(a1+2)*inf)/(b3*(b2+1)+(b1+2)*inf))
求极限也就是比较上下两个式子的大小，如果上面大于下面，实际是上面小于下面（没去log实际的值），则结果是趋向于0，输出-1
类似，上面小于下面，输出1，上面等于下面，输出0
接下来看怎么比较a3*(a2+1)+(a1+2)*inf和b3*(b2+1)+(b1+2)*inf
注意这个比较是建立在log上的，所以我们应该先找出较小的一对数，两对数：(a3,a2+1),(a1+2,inf)
我们先排序好每对数，每对数里再排序好两个数，然后直接遍历比较大小
AC代码：
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define ls (r<<1)
#define rs (r<<1|1)
#define debug(a) cout << #a << " " << a << endl
using namespace std;
typedef long long ll;
const ll maxn = 1e5+10;
const double eps = 1e-8;
const ll mod = 998244353;
const int inf = 0x3f3f3f3f;
const double pi = acos(-1.0);
void getmin(ll *a) {
if( min(a[0],a[1]) == min(a[2],a[3]) ) {
if( max(a[0],a[1]) >= max(a[2],a[3]) ) {
swap(a[0],a[2]), swap(a[1],a[3]);
}
} else if( min(a[0],a[1]) > min(a[2],a[3]) ) {
swap(a[0],a[2]), swap(a[1],a[3]);
}
if( a[0] > a[1] ) {
swap(a[0],a[1]);
}
if( a[2] > a[3] ) {
swap(a[2],a[3]);
}
}
int main() {
ios::sync_with_stdio(0);
ll T;
cin >> T;
while( T -- ) {
ll a, b, A[4] = {0}, B[4] = {0};
cin >> a >> b;
for( ll i = 1; i <= a; i ++ ) {
cin >> A[i];
}
for( ll i = 1; i <= b; i ++ ) {
cin >> B[i];
}
A[0] = inf, B[0] = inf;
for( ll i = 1; i <= 3; i ++ ) {
if(A[i]) {
A[i] += 3-i;
} else {
A[i] = inf;
}
if(B[i]) {
B[i] += 3-i;
} else {
B[i] = inf;
}
}
getmin(A),getmin(B);
ll ans = 0;
for( ll i = 0; i <= 3; i ++ ) {
if( A[i] == B[i] ) {
continue;
}
if( A[i] < B[i] ) {
ans = 1;
break;
} else if( A[i] > B[i] ) {
ans = -1;
break;
}
}
cout << ans << endl;
}
return 0;
}