原题链接
和之前的统计单词个数十分类似 将前面的分为两部分 一部分是前面的人抄的 剩下的是自己抄的 取max
和原时间取min
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<cmath> #include<queue> #include<vector> #include<climits> #include<string> #include<cstdlib> #include<map> #include<ctime> #define MAX 1000000007 #define LL long long using namespace std; int m,k,bok[505],i,d[505],j,g,f[505][505],t,b,human[505],s[505],e[505]; int main() { memset(f,127,sizeof(f)); scanf("%d%d",&m,&k); for(i=1;i<=m;i++) { scanf("%d",&bok[i]); f[i][0]=0; f[1][i]=f[1][i-1]+bok[i]; d[i]=d[i-1]+bok[i]; } for(i=1;i<=k;i++) for(j=1;j<=m;j++) for(g=1;g<j;g++) f[i][j]=min(f[i][j],max(f[i-1][g],d[j]-d[g])); t=f[k][m]; b=m; for(i=k;i>=1;i--) for(j=b;j>=1;j--) { if(human[i]+bok[j]>t) { b=j; e[i]=j+1; break; } else { if(!human[i]) s[i]=j; human[i]+=bok[j]; } } if(!e[1]) e[1]=1; for(i=1;i<=k;i++) printf("%d %d\n",e[i],s[i]); return 0; }