hiho模拟面试题2

#include<iostream>
#include<string>
#include<vector>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;

unsigned int CalContinuousDays(bitset<101>& bitvec){
unsigned int max=0,left,right,ix=1;
while(ix<bitvec.size()){
if(!bitvec.test(ix))
{
ix++;
continue;
}
left=ix;
right=ix+1;
while(right<bitvec.size() && bitvec.test(right))
right++;
int curMax=right-left;
if(curMax>max)
max=curMax;
ix=right+1;

}
return max;
}

void combination(int* set,int n,int k,vector<int>& final,vector<int>srcData){
vector<int>vec(n);
for(vector<int>::size_type ix=0;ix<vec.size();ix++)
if(ix<k)
vec[ix]=1;
else
vec[ix]=0;

vector<int>subset(k);

bool has_next=true;
while(has_next){
int j=0;
for(vector<int>::size_type ix=0;ix<n;ix++){
if(vec[ix]==1)
subset[j++]=set[ix];
}

bitset<101>bitvec;
bitvec.set();

vector<int>::const_iterator iter1=srcData.begin();
for(;iter1!=srcData.end();iter1++ )
bitvec.reset(*iter1);

vector<int>::iterator iter=subset.begin();
for(;iter!=subset.end();iter++)
bitvec.set(*iter);

unsigned int maxCD=CalContinuousDays(bitvec);

final.push_back(maxCD);

has_next=false;
for(vector<int>::size_type ix=0;ix<vec.size()-1;ix++){
if(vec[ix]==1 && vec[ix+1] == 0){
vec[ix]=0;
vec[ix+1]=1;


int count=0;
for(vector<int>::size_type ix2=0;ix2<ix;ix2++){
if(vec[ix2]==1)
count++;
}

if(count<=ix){
for(vector<int>::size_type ix3=0;ix3<ix;ix3++){
if(ix3<count)
vec[ix3]=1;
else
vec[ix3]=0;
}
}
has_next=true;
break;
}
}
}
}

int main()
{
clock_t start=clock();
int T,N,M;
freopen("input.txt","r",stdin);
cin>>T;

while(T--){
cin>>N>>M;

int* nums=new int[N+1];
*(nums+N)=-1;

for(int i=0;i<N;i++)
cin>>*(nums+i);

if(M>=N){
cout<<100<<endl;
continue;
}

vector<int>final;
vector<int>srcData(N);
int k=0;
for(vector<int>::size_type ix=0;ix<srcData.size();ix++)
srcData[ix]=*(nums+(k++));
combination(nums,N,M,final,srcData);

int max=*max_element(final.begin(),final.end());
cout<<max<<endl;
final.clear();

delete []nums;

}

clock_t end=clock();
cout<<(double) (end-start)/ CLOCKS_PER_SEC;
return 0;
}