洛谷 P2141 [NOIP2014 普及组] 珠心算测验

本文由Jzwalliser原创，发布在CSDN平台上，遵循CC 4.0 BY-SA协议。
因此，若需转载/引用本文，请注明作者并附原文链接，且禁止删除/修改本段文字。
违者必究，谢谢配合。
个人主页：blog.csdn.net/jzwalliser

题目

洛谷 P2141 [NOIP2014 普及组] 珠心算测验

[NOIP2014 普及组] 珠心算测验

题目背景

NOIP2014 普及 T1

题目描述

珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练，既能够开发智力，又能够为日常生活带来很多便利，因而在很多学校得到普及。

某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合，集合中的数各不相同，然后要求学生回答：其中有多少个数，恰好等于集合中另外两个（不同的）数之和？

最近老师出了一些测验题，请你帮忙求出答案。

输入格式

共两行，第一行包含一个整数 $n$，表示测试题中给出的正整数个数。

第二行有 $n$ 个正整数，每两个正整数之间用一 个空格隔开，表示测试题中给出的正整数。

输出格式

一个整数，表示测验题答案。

样例 #1

样例输入 #1

4
1 2 3 4

样例输出 #1

2

提示

【样例说明】

由 $1+2=3,1+3=4$，故满足测试要求的答案为 $2$。

注意，加数和被加数必须是集合中的两个不同的数。

【数据说明】

对于 $100\%$ 的数据，$3\le n\le 100$，测验题给出的正整数大小不超过 $10,000$。

想法

这道题，我还是喜欢倒着来，与其找数字相加找和是否在列表中，还不如用大数字减小数字，检查差是否在列表中。
所以，先写一个函数inside()，用于检查某一个数是否在列表中，后面调用起来方便。
同时注意，不可以出现$a+a=b$的情况，比如样例中虽然$2+2=4$，但这不能算是合法的，因为数字$2$被“重复利用”了。

实现

1. 输入。
2. 从最大的数开始试，一一减去比它小的数，并检查差是否在列表中。同时注意，差不能等于减数。如果满足以上规则就计数器+1。
3. 输出计数器中的数。

题解

C++

#include<bits/stdc++.h>
using namespace std;
int sum = 0; //计数器初始化
int num[105]; //输入做多100个数
int n;
bool inside(int search){ //检查数字是否在列表中的函数
	for(int i = 0;i < n;i++){ //遍历列表
		if(num[i] == search){ //如果在就返回true
			return true;
		}
	}
	return false; //否则返回false
}

int main(){
	cin >> n;
	for(int i = 0;i < n;i++){
		cin >> num[i]; //输入
	}
	sort(num + 0,num + n); //排序
	for(int i = n - 1;i >= 0;i--){ //从最大的数开始作为被减数
		for(int j = 0;j < i;j++){ //比当前数小的数作为减数
			if(inside(num[i] - num[j]) and num[i] - num[j] != num[j]){ //差也是列表中数，且差不等于减数
				sum += 1; //计数器加一
				break; //既然已经找到了那就退出循环，继续下一个数，以防浪费时间
			}
		}
	}
	cout << sum; //输出
	return 0;
}

Python

sum = 0 #计数器初始化
n = int(input())
num = input().split()
for i in range(len(num)):
	num[i] = int(num[i])
num.sort() #排序

for i in reversed(range(n)): #从最大的数开始作为被减数
	for j in range(i): #比当前数小的数作为减数
		if (num[i] - num[j]) in num and num[i] - num[j] != num[j]: #差也是列表中数，且差不等于减数
			sum += 1; #计数器加一
			break; #既然已经找到了那就退出循环，继续下一个数，以防浪费时间
print(sum) #输出

难度

难度：★☆☆☆☆
这道题其实还好吧，只是稍有些思维难度。

结尾

这道题你是怎么AC的？欢迎讨论！欢迎批评！