PK赛
- 总时间限制:
- 1000ms
- 内存限制:
- 65535kB
- 描述
-
在一次学校的活动中，有一个老师和学生的PK。其中ai是教师的得分和bi为学生的得分。
如果ai+aj>bi+bj(即老师胜)，问最后老师胜的次数是多少次？ - 输入
-
多组数据输入的第一行包含一个整数n (2≤n≤2*10^5)——评分的数量。输入的第二行包含n个整数a1,a2，…，an(1≤ai≤109)，其中ai为教师第i个评分。输入的第三行包含n个整数b1,b2，…，bn(1≤bi≤109)，其中bi为学生第i个评分。
- 输出
-
打印一个整数老师胜利的数量。
- 样例输入
-
5 4 8 2 6 2 4 5 4 1 3 4 1 3 2 4 1 3 2 4
- 样例输出
-
7 0
一开始是这样写的,结果显示超时
1 #include<iostream>
2 #include<cstdio>
3 #define Maxn 100000
4 using namespace std;
5
6 int com[Maxn],t[Maxn],s[Maxn];
7 int main()
8 {
9 int n;
10 int cnt;
11 while(cin>>n)
12 {
13 cnt=0;
14 for(int j=0;j<n;++j) scanf("%d",&t[j]);
15 for(int j=0;j<n;++j){
16 scanf("%d",&s[j]);
17 com[j]=t[j]-s[j];
18 }
19 for(int i=0;i<n-1;++i)
20 {
21 for(int j=i+1;j<n; ++j)
22 {
23 if(com[i]+com[j]>0){
24 cnt++;
25 }
26 }
27 }
28 cout<<cnt<<endl;
29 }
30 return 0;
31 }
经过查询,用lower_bound( )会省去很多时间
lower_bound( )和upper_bound( )
转载自:关于lower_bound( )和upper_bound( )的常见用法_brandong-CSDN博客_lower_bound
lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。
在从小到大的排序数组中，
lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
在从大到小的排序数组中，重载lower_bound()和upper_bound()
lower_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
upper_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int maxn=100000+10;
4 const int INF=2*int(1e9)+10;
5 #define LL long long
6 int cmd(int a,int b){
7 return a>b;
8 }
9 int main(){
10 int num[6]={1,2,4,7,15,34};
11 sort(num,num+6); //按从小到大排序
12 int pos1=lower_bound(num,num+6,7)-num; //返回数组中第一个大于或等于被查数的值
13 int pos2=upper_bound(num,num+6,7)-num; //返回数组中第一个大于被查数的值
14 cout<<pos1<<" "<<num[pos1]<<endl;
15 cout<<pos2<<" "<<num[pos2]<<endl;
16 sort(num,num+6,cmd); //按从大到小排序
17 int pos3=lower_bound(num,num+6,7,greater<int>())-num; //返回数组中第一个小于或等于被查数的值
18 int pos4=upper_bound(num,num+6,7,greater<int>())-num; //返回数组中第一个小于被查数的值
19 cout<<pos3<<" "<<num[pos3]<<endl;
20 cout<<pos4<<" "<<num[pos4]<<endl;
21 return 0;
22 }
所以,最后是这样写的
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn=200006;
5 ll a[maxn],b[maxn],c[maxn];
6 int main() {
7 int n;
8 while(cin>>n)
9 {
10 for(int i=1; i<=n; i++) cin>>a[i];
11 for(int i=1; i<=n; i++) {
12 cin>>b[i];
13 c[i]=a[i]-b[i];
14 }
15 sort(c+1,c+n+1);
16 ll sum=0;
17 for(int i=1; i<=n; i++) {
18 ll k=upper_bound(c+i+1,c+n+1,-c[i])-c;
19 sum+=n-k+1;
20 }
21 cout<<sum<<endl;
22 }
23 return 0;
}