#include
#include
#include
using namespace std;
bool search(vector,int,int);
int main()
{
int n,k;
cin>>n>>k;
vectora;
int sum=0;
for(size_t i=0;i!=n;++i)
{
int temp;cin>>temp;
sum+=temp;
a.push_back(temp);
}
int left=sum/k,right=sum;
int x;
while(left
{
x=(left+right)/2;
if(search(a,x,k))//分隔以后，每一段和都
right=x;
else left=x+1;//不符合时，增加左边界
}
vector::reverse_iterator iter=a.rbegin();
sum=0;
deque::reverse_iterator>solve;
while(iter!=a.rend())
{
if(iter-a.rend()-1==k-1-solve.size())
{
solve.push_front(iter);
++iter;
}
else if(sum+*iter<=x)
sum+=*iter;
else
{
sum=*iter;
solve.push_front(iter);
}
++iter;
}
for(vector::iterator iter=a.begin();iter!=a.end();++iter)
{
if(!solve.empty()&&iter==solve.front().base())
{
cout<<"| ";
solve.pop_front();
}
cout<<*iter<<" ";
}
while(1);
}
bool search(vector a,int x,int k)
{
int sum=0;
vector::reverse_iterator iter=a.rbegin();
while(iter!=a.rend())
{
if(sum+*iter<=x)
sum+=*iter;
else
{
if(k==1)return false;
--k;sum=*iter;
}
++iter;
}
return true;
}
这段代码中，运行到
else
{
sum=*iter;
solve.push_front(iter);
}
这一段的时候，为什么，感觉*iter显示总是慢一步，调试的时候，发现sum变成6了，为什么,solve中写的size是1，然后[0]对应 reverse_iterator current 5,为什么不是6
