欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

7-12 小猪佩奇之自来水厂(20 分)

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

佩奇家的村庄有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 }