题目描述
有长度为n的街道 有m个人 大家一起捡垃圾
下面有n个整数a[i]，表示在第i点有a[i]个垃圾
我们在起点0处 每前进一步需要1秒，一次只能捡一个垃圾并且耗时1秒
问你最快需要多少时间能够捡完
输入
多实例 n,m (0<n<=1000)(0<m<=2000)<n<=1000)(0<m<=2000)<n<=1000) (0<m<="2000)
下面n个整数表示在i位置有a[i]个垃圾 (0<=a[i]<1000)
输出
最小的耗时
样例输入
复制
6 2 1 1 1 1 1 1 6 1 1 1 1 1 1 1
样例输出
复制
8 12
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<queue> #include<map> #include<vector> #include<math.h> using namespace std; #define INF 0x3f3f3f3f #define LL long long #define N 1006 int n,m,a[N],w[N]; int q(int xx) {for(int i=1; i<=n; i++)a[i]=w[i];for(int j=1; j<=m; j++){int x=xx;int ans=0;for(int i=n; i>=1&&x>0; i--){if(a[i]==0) continue;if(!ans)x-=i;ans=1;if(a[i]&&x>=a[i]){x=x-a[i];a[i]=0;}else if(a[i]&&x>0){a[i]=a[i]-x;x=0;}}}for(int i=1; i<=n; i++){if(a[i])return 1;}return 0; } int main() {while(scanf("%d%d",&n,&m)!=EOF){for(int i=1; i<=n; i++)scanf("%d",&w[i]);int l=0,r=INF;while(l<r){int mid=(l+r)/2;if(q(mid))l=mid+1;else r=mid;}printf("%d\n",l);}return 0; }