首页 > > 程序设计 > C/C++ >

7-12 小猪佩奇之自来水厂（20 分）

2018-06-17 20:28:40来源：未知阅读 ()

佩奇家的村庄有N户人家，每户每天用水量为 Ni L，一天，佩奇和弟弟乔治去自来水厂参观，发现为了配送方便，自来水厂采用统一规格的水桶，水桶容量为C，同时需要保证每户得到的桶数为整数(不可以配送半桶)，佩奇想知道自来水厂每天至少需要准备多少桶水，聪明的你能帮佩奇计算，水厂每天至少需要水的桶数吗

输入格式:

输入分为两行，第一行输入一个整数N(1<=N<=1000000),表示村庄户数，第二行输入N个整数(1<=Ni<=1000000)

输出格式:

输出共一行，一个整数，表示水厂最少需要准备水的桶数

输入样例:

在这里给出一组输入。例如：

6
4 8 12 16 4 20

输出样例:

在这里给出相应的输出。例如：

16

这道题非常有意思，读了好多遍，wa了好几次，最后发现，就是求一堆数的最大公约数。
所以这道题就非常简单了

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <string>
 4 #include <string.h>
 5 typedef long long ll;
 6 using namespace std;
 7 
 8 ll gcd(ll a,ll b)
 9 {
10      if(a % b == 0)
11           return b;
12      return gcd(b,a%b);
13 }
14 int main()
15 {
16     
17     ll n;
18     cin >> n;
19     ll a[n];
20     ll sum = 0;
21     for(ll i = 0; i < n; i++) {
22         ll x;
23         cin >> x;
24         a[i] = x;
25         sum += x;
26     }
27     ll m = a[0];
28     for(ll i = 1; i < n; i++) {
29         m = gcd(m, a[i]);
30     }
31     //cout << m;
32     ll c = 0;
33     for(ll i = 0; i <n; i++) {
34         c += a[i]/m; 
35     }
36     cout << c;
37 }