Raul
BAN USERWhat about expanding the vector and simply iterate throughout it?
#include <iostream>
#include <vector>
#include <map>
std::map<int, bool>expandVector(const std::vector<int> &v) {
if (v.size() == 0)
return std::map<int, bool>();
std::map<int, bool> result;
int i = 0;
while (i<v.size()) {
result.insert(std::pair<int, bool>(v.at(i), true));
if ((i+1) == v.size())
return result;
for (int j=v.at(i);j<v.at(i+1);j++)
result.insert(std::pair<int, bool>(j, false));
i++;
}
return result;
}
int minNumberOfBlocks(int rollarLength, const std::vector<int> &v) {
std::map<int, bool> expandedRoad = expandVector(v);
std::map<int, bool>::iterator it = expandedRoad.begin();
int newPos = it->first + rollarLength;
++it;
int blocksCovered = 1;
for (; it!=expandedRoad.end(); ++it) {
std::cout << "new pos: " << newPos << std::endl;
if (it->first <= newPos) {
blocksCovered++;
std::cout << "Processing " << it->first << " blocks covered " << blocksCovered<< std::endl;
}
else if (it->first > newPos)
if (it->second == true) {
newPos = it->first + rollarLength;
blocksCovered++;
std::cout << "Processing " << it->first << " blocks covered " << blocksCovered<< std::endl;
} else {
std::cout << "Jumping " << it->first << std::endl;
}
}
return blocksCovered;
}
int main() {
std::vector<int> v;
v.push_back(2);
v.push_back(3);
v.push_back(6);
//v.push_back(10);
/*std::map<int, bool> expanded = expandVector(v);
std::map<int, bool>::iterator it;
for (it=expanded.begin(); it!=expanded.end(); ++it)
std::cout << it->first << " => " << it->second << std::endl;*/
std::cout << "number of blocks " << minNumberOfBlocks(3, v);
}
- Raul June 19, 2016