NC25188. 小蚂蚁过马路
描述
输入描述
第一行一个整数T(T <=
6)，表示数据组数。
在每组输入数据中，第一行有2个正整数，n(n <= 1e15)，K(2<=K<=1e5)，分别表示小蚂蚁的数量和城市的数量。
第二行中有K - 1个正整数a[i](a[i] <= 1e15)，表示从城市i到城市i+1同一时间最多能通过几只小蚂蚁。
输出描述
对于每组数据，输出一个数ans，表示所有蚂蚁到达城市K所需要的时间。
示例1
输入:
2 16 3 6 5 15 3 6 5
输出:
5 4
说明:
第二组样例，第一个单位时间有6只蚂蚁从城市1到城市2，第二个单位时间有5只城市2的蚂蚁到城市3，同时又有6只蚂蚁从城市1到城市2，此时，有3只蚂蚁在城市1,7只蚂蚁在城市2,5只蚂蚁在城市3，第3个单位时间里，C++14(g++5.4) 解法, 执行用时: 114ms, 内存消耗: 352K, 提交时间: 2019-04-21 21:08:51
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ll t;
cin>>t;
while(t--){
ll n,k;
cin>>n>>k;
ll m,p;
cin>>m;
for(ll i=1;i<k-1;i++){
cin>>p;
if(p<m)m=p;
}
ll ans;
if(n%m)ans=n/m+1;
else ans=n/m;
cout<<ans-1+k-1<<endl;
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 57ms, 内存消耗: 468K, 提交时间: 2020-02-26 13:28:23
#include<bits/stdc++.h>
using namespace std;
long long t,n,m,minn,x;
int main()
{
cin>>t;
while(t--)
{
cin>>m>>n;
minn=1e16;
for(int i=1;i<n;i++)
{
scanf("%lld",&x);
minn=min(minn,x);
}
printf("%lld\n",(n-1)+(m-1)/minn);
}
}
Python3(3.5.2) 解法, 执行用时: 167ms, 内存消耗: 18332K, 提交时间: 2019-04-21 12:44:43
T=int(input())
for t in range(T):
n,m=map(int,input().split())
A=list(map(int,input().split()))
print(m-1+(n-1)//min(A))