共计 764 个字符,预计需要花费 2 分钟才能阅读完成。
找到 n 个数中两个数之和为 7 的对数
//(相比两层 for 循环工夫复杂度仅为 O(N) 的改良算法 )
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<cstdio>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
using namespace std;
int main(){
int n;// 要输出 n 个数来找和为 7 的数的数对
scanf("%d",&n);
long long num[20];// 定义一个数组去存 %7 取余后余数为 i 的个数,20 是随便定的,>= 7 就行,因为任何数对 7 取余都小于 7
for(int i = 0; i < 20; i++){num[i] = 0;// 初始化一下,%7 余数为 i 的个数都是 0
}
for(int i = 1; i <= n; i++){
int x;// 输出 n 个数
scanf("%d",&x);
num[x%7]++;// 记录余数为某个数 i 的个数,更新对应的 num[i] 的值来记录
}
long long sum = 0;
sum += (num[0] *(num[0] - 1)/2);// 对 7 取余为 0 的比拟非凡(因为 14+14,7+ 7 等满足条件但却不是一对数 (应为不等的一对数))// 故满足条件的数是 7,14,21 等排列组合失去的个数为 n *(n-1)/2
sum += (num[1] * num[6]);// 对 7 取余为 1 的个数与对 7 取余为 6 的个数相乘失去 1 和 6 总对数(对 7 取余为 1 的数与对 7 取余为 6 的数相加必定是 7 的倍数)sum += (num[2] * num[5]);// 同理
sum += (num[3] * num[4]);// 同理
printf("%lld\n",sum);
return 0;
}
正文完