题解：投票人数统计问题

题目分析

我们有 $N$ 个比例 $P_i$，它们四舍五入到小数点后 $L$ 位。
我们需要找到最小的正整数 $K$，使得存在非负整数 $D_1, \dots, D_N$ 满足：

1. 比例约束：

   $$P_i - \frac12 \times 10^{-L} \le \frac{D_i}{K} < P_i + \frac12 \times 10^{-L} $$

2. 整数约束：$D_i$ 是非负整数

3. 总和约束：$\sum_{i=1}^N D_i = K$

---

数学转换

将比例约束转换为 $D_i$ 的范围：

$$K \cdot \left(P_i - \frac12 \times 10^{-L}\right) \le D_i < K \cdot \left(P_i + \frac12 \times 10^{-L}\right) $$

设：

• $L_i = \lceil K \cdot (P_i - 0.5 \times 10^{-L}) \rceil$（下界向上取整，因为 $D_i$ 是整数）
• $R_i = \lfloor K \cdot (P_i + 0.5 \times 10^{-L}) \rfloor$（上界向下取整）

我们需要：

$$L_i \le D_i \le R_i \quad \text{且} \quad \sum_{i=1}^N D_i = K $$

---

解的存在条件

对于给定的 $K$，解存在的充要条件是：

$$\sum_{i=1}^N L_i \le K \le \sum_{i=1}^N R_i$$

证明：

• 如果 $\sum L_i > K$，那么即使每个 $D_i$ 都取下界，总和也超过 $K$，无解。
• 如果 $\sum R_i < K$，那么即使每个 $D_i$ 都取上界，总和也不够 $K$，无解。
• 如果 $\sum L_i \le K \le \sum R_i$，我们可以从 $D_i = L_i$ 开始，逐步增加某些 $D_i$（不超过 $R_i$）直到总和等于 $K$。

---

算法设计

由于 $K$ 可能很大，我们需要高效地找到最小的 $K$：

1. 确定搜索范围：

   • 最小可能的 $K$：$K_{\min} = 1$
   • 最大可能的 $K$：由于 $L \le 6$，$K$ 不会太大（实际上样例中最大为 7766）
   • 我们可以从 $K = 1$ 开始枚举，直到找到解

2. 验证函数： 对于每个 $K$，计算：

   • $L_i = \lceil K \cdot (P_i - 0.5 \times 10^{-L}) \rceil$
   • $R_i = \lfloor K \cdot (P_i + 0.5 \times 10^{-L}) \rfloor$ 然后检查 $\sum L_i \le K \le \sum R_i$

3. 浮点精度处理： 为了避免浮点误差，我们可以用整数运算：

   • 将 $P_i$ 转换为整数：$P_i = \frac{\text{分子}_i}{10^L}$
   • 那么 $K \cdot P_i = \frac{K \cdot \text{分子}_i}{10^L}$
   • 使用高精度整数或分数运算

---

具体步骤

1. 解析输入：

   • 读取每个 $P_i$ 字符串，确定小数位数 $L$
   • 将 $P_i$ 转换为整数分子：$A_i = \text{round}(P_i \times 10^L)$

2. 枚举 $K$：

   • 从 $K = 1$ 开始递增
   • 对于每个 $i$：
     • 下界：$ \text{lower}_i = \lceil \frac{K \cdot A_i - 5 \times 10^{L-1}}{10^L} \rceil $
     • 上界：$ \text{upper}_i = \lfloor \frac{K \cdot A_i + 5 \times 10^{L-1} - 1}{10^L} \rfloor $
     • 注意：$D_i$ 必须是非负整数，所以下界不能小于 0

3. 检查可行性：

   • 如果所有 $\text{lower}_i \le \text{upper}_i$ 且 $\sum \text{lower}_i \le K \le \sum \text{upper}_i$，则找到解

---

复杂度分析

• 最坏情况下 $K$ 可能达到 $10^L$ 量级
• 对于 $L \le 6$，$K \le 10^6$ 是可接受的
• 每个 $K$ 的验证是 $O(N)$
• 总复杂度 $O(N \cdot K_{\max})$，在数据范围内可行

---

样例验证

样例 1：

3
0.166667  # 1/6
0.333333  # 1/3  
0.500000  # 1/2

$L=6$，枚举 $K$：

• $K=6$ 时：$D_1 \in [0.5, 1.5) \Rightarrow [1,1]$，$D_2 \in [1.5, 2.5) \Rightarrow [2,2]$，$D_3 \in [2.5, 3.5) \Rightarrow [3,3]$
• 总和 $1+2+3=6$，满足条件

---

代码实现

import math

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    P_str = data[1:1+N]
    
    # 确定小数位数 L
    L = max(len(p.split('.')[1]) if '.' in p else 0 for p in P_str)
    
    # 转换为整数分子
    A = []
    for p in P_str:
        if '.' in p:
            integer, decimal = p.split('.')
            decimal = decimal.ljust(L, '0')[:L]
            numerator = int(integer + decimal) if integer != '0' else int(decimal)
        else:
            numerator = int(p) * (10 ** L)
        A.append(numerator)
    
    K = 1
    while True:
        lower_sum = 0
        upper_sum = 0
        valid = True
        
        for a in A:
            # 计算下界: ceil((K*a - 5*10^(L-1)) / 10^L)
            lower = (K * a - 5 * 10**(L-1) + 10**L - 1) // 10**L
            lower = max(lower, 0)  # 非负
            
            # 计算上界: floor((K*a + 5*10^(L-1) - 1) / 10^L)
            upper = (K * a + 5 * 10**(L-1) - 1) // 10**L
            
            if lower > upper:
                valid = False
                break
                
            lower_sum += lower
            upper_sum += upper
        
        if valid and lower_sum <= K <= upper_sum:
            print(K)
            return
            
        K += 1

if __name__ == "__main__":
    main()

---

优化

实际上，由于 $K$ 不会太大，直接枚举是可行的。
如果 $K$ 可能很大，我们可以用中国剩余定理或连分数来加速搜索，但本题数据范围下枚举足够。

---

总结

本题的关键在于：

1. 将四舍五入的比例约束转换为整数范围约束
2. 利用求和条件 $\sum L_i \le K \le \sum R_i$ 判断解的存在性
3. 通过枚举 $K$ 找到最小解

这是一个典型的数论+枚举问题，考察对浮点精度和整数约束的理解。