ACM 寻找思路
描述
出去春游一趟回来后，ZZ带回来很多礼物。每个礼物有一个价值。他将所有礼物排成一列，并将这些礼物分成M份，每一份是由一个或多个礼物组成的连续的序列。他要将这M份礼物分别送给他的M个朋友。这样的划分有个要求，那就是使总价值最大的片段的总价值尽量小。
输入
第一行为两个整数N(1<=N<=100,000)，M(1<=M<=N)。接下来N行按顺序给出每个物品的价值v(1<=v<=10,000)
输出
输出为一个整数，为满足题目条件的最大的连续序列的总价值
样例输入
7 5
100
400
300
100
500
101
400
样例输出
500
有谁知道很好的算法，说出来大家分享一下吧
[解决办法]
礼物顺序应该是固定好了：下面这个代码应该可以，没验证，呵呵
#include<iostream>
using namespace std;
int main()
{
int n,m,v[10000];int i,j;int sum=0;int ss=0;int s=0;int max_min;
cin>>n>>m;
for(i=0;i<n;++i){cin>>v[i];sum+=v[i];}
double av=(double)(sum/m);
max_min=-10000;
for(i=0;i<n;i++)
if(v[i]>av)
{
if(max_min<v[i])
{max_min=v[i];s=1; }
}
if(s==0)
{
max_min=100000000;
for(i=0;i<n;++i)
{
ss=0;
for(j=i;j<n;++j)
{
ss+=v[j];
if(ss>av)
{
if(max_min>ss)max_min=ss;
break;
}
}
}
}
cout<<max_min<<endl;
return 0;
}
