hantasm
BAN USERA recursive solution.
#include <iostream>
using namespace std;
int min_time(int h_left, int m_left, int h_num,
int m_num, int holes[], int mice[]) {
while(h_left <= 216 && holes[h_left] == 0) h_left++;
if (h_left > 216) return 0;
while(m_left <= 216 && mice[m_left] == 0) m_left++;
if (m_left > 216) return 0;
//not skip
int curr = abs(h_left - m_left);
mice[m_left]--;
int rest = min_time(h_left + 1, m_left, h_num - 1,
m_num - 1, holes, mice);
mice[m_left]++;
int no_skip = max(curr, rest);
if (m_left <= h_left || h_num == m_num) {
return no_skip;
}
else {
//skip
int skip = min_time(h_left + 1, m_left, h_num - 1,
m_num, holes, mice);
return min(no_skip, skip);
}
}
void get_min_time(void) {
int n, m;
cin>>n>>m;
int mice[217], holes[217];
memset(mice, 0, 217*sizeof(int));
memset(holes, 0, 217*sizeof(int));
for (int i = 0; i < n; i++) {
int temp;
cin>>temp;
mice[108+temp]++;
}
for (int i = 0; i < m; i++) {
int temp;
cin>>temp;
holes[108+temp]++;
}
cout<<"Min time: "<<min_time(0, 0, m, n, holes, mice)<<endl;
}
int main() {
int T;
cin>>T;
for (int i = 0; i < T; i++) get_min_time();
return 0;
}
DP will be more effective.
- hantasm September 28, 2014
- hantasm January 03, 2015