题解：Doubles（P1552）

一、题目分析

本题要求计算数字列表中满足“某数是其他数两倍”的项数。核心要点：

• 对于列表中每个数x，检查是否存在另一个数y，使得x=2y
• 统计所有符合条件的x的数量
• 每个列表以0结尾，输入以-1结束

二、代码解析（C++实现）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

bool cmp(int a, int b) { 
    return a > b;  // 降序排序
}

int num[1010];  // 存储数字列表
char s[10000010];
char c, d;

int main() {
    int pos = 0, ans = 0;
    c = 'a';  // 初始化字符变量
    
    while (~scanf("%d%c", &num[++pos], &c) && num[1] != -1) {
        // 读取当前列表所有数字，直到遇到换行符
        while (c != '\n') {
            scanf("%d", &num[++pos]);
            scanf("%c", &c);
        }
        
        // 降序排序数字列表
        sort(num + 1, num + 1 + pos, cmp);
        
        // 遍历查找满足x=2y的数对
        ans = 0;
        for (int i = 1; i < pos; i++) {
            for (int j = i + 1; j <= pos; j++) {
                if (num[j] * 2 == num[i]) {
                    ans++;
                    break;  // 找到一个匹配后跳出内层循环
                }
            }
        }
        
        // 输出结果并重置变量
        printf("%d\n", ans);
        pos = 0;
        ans = 0;
        c = 'a';
    }
    return 0;
}

三、关键步骤解析

1. 输入处理

   • 使用&scanf("%d%c", &num[++pos], &c)&读取数字和其后的字符（空格或换行符）
   • 当&c != '\n'&时，继续读取后续数字，直到遇到换行符表示当前列表结束
   • 输入以&num[1] == -1&作为结束标志

2. 排序优化

   • 对数字列表进行降序排序，使得较大的数在前，较小的数在后
   • 降序排列后，只需检查&num[j] * 2 == num[i]&（j > i），因为&num[i]&是较大数

3. 结果统计

   • 每找到一个满足条件的x，ans加1
   • 每个列表处理完毕后输出ans，并重置变量

四、算法优化

1. 排序的作用
   降序排序后，只需检查$num[j] * 2 = num[i]$（j > i），确保每个x只被较小的y匹配一次，避免重复计算。

2. 提前终止内层循环
   当找到一个y使得$num[j] * 2 = num[i]$时，立即跳出内层循环，减少不必要的判断。

3. 时间复杂度

   • 排序：O(n log n)，n为列表长度（n≤15）
   • 双重循环：O(n²)
   • 总体复杂度：O(n log n + n²)，完全满足1000ms时间限制

五、示例解析

以输入列表$1 4 3 2 9 7 18 22 0$为例：

1. 排序后列表为：22, 18, 9, 7, 4, 3, 2, 1
2. 遍历检查：
   • i=1（22）：j从2开始，22/2=11，列表中无11 → 不匹配
   • i=2（18）：j=3（9），9×2=18 → 匹配，ans=1
   • i=3（9）：j>3的数中无4.5 → 不匹配
   • i=4（7）：无3.5 → 不匹配
   • i=5（4）：j=7（2），2×2=4 → 匹配，ans=2
   • i=6（3）：无1.5 → 不匹配
   • i=7（2）：j=8（1），1×2=2 → 匹配，ans=3
3. 最终输出3，与示例一致

六、注意事项

1. 输入结束条件
   程序通过$num[1] != -1$判断是否读取到输入结束标记，需确保第一个数字不为-1。

2. 数字范围
   题目中所有数字≤99，因此无需处理大数溢出问题。

3. 去重处理
   题目保证列表中的数字不同，因此无需额外去重。

4. 循环边界
   内层循环从j=i+1开始，避免同一个数自我比较（题目要求“其他某项”）。

七、可能的改进

使用集合优化
将数字存入集合，遍历每个数x时，直接检查x/2是否存在，时间复杂度可优化至O(n)。