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 }
上一篇: 我待会买彩票能中五百万你信吗
下一篇: 记一次学习PHP中的错误