このSPOJ 問題の解決策を C++11 で実装しました。使用すると完全にコンパイルされますclang
。SPOJ のg++
送信では、メッセージとともに実行時エラーをスローする使用が使用されますinvalid pointer
。私はそれを次の行に絞り込みました:
studentNumberToRequestedBedroomsMap.clear();
他の回答から、解放されるポインターが によって取得されたものではない場合にこのエラーが発生することを理解しましたmalloc
が、私はまだ C++ に慣れていないため、その情報を使用してこの問題を解決する方法がわかりません。この問題の解決にご協力いただければ幸いです。
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <set>
#include <algorithm>
#define INDEX(bedNumber) (bedNumber - 1)
int main() {
std::string input = "3\n"
"3 3\n"
"1 1\n"
"2 1\n"
"2 2\n"
"3 2\n"
"3 3\n"
"0 0\n"
"4 3\n"
"1 1\n"
"1 3\n"
"2 1\n"
"3 1\n"
"3 2\n"
"4 2\n"
"0 0\n"
"4 2\n"
"1 1\n"
"1 2\n"
"2 1\n"
"2 2\n"
"3 1\n"
"3 2\n"
"4 1\n"
"4 2\n"
"0 0";
std::istringstream inputString(input);
int lineNumber;
std::string line;
std::set<int> assignedBedrooms;
std::vector<std::vector<int>> studentNumberToRequestedBedroomsMap;
std::vector<int> bedroomDemand;
while (getline(inputString, line)) {
++lineNumber;
std::stringstream lineStream(line);
if (lineNumber == 1) {
continue;
}
if (bedroomDemand.empty()) {
int numberOfStudents;
lineStream >> numberOfStudents;
int numberOfBeds;
lineStream >> numberOfBeds;
bedroomDemand.resize(numberOfBeds);
std::fill(bedroomDemand.begin(), bedroomDemand.end(), 0);
// initialize studentNumberToRequestedBedroomsMap
studentNumberToRequestedBedroomsMap.resize(numberOfStudents);
std::fill(studentNumberToRequestedBedroomsMap.begin(),studentNumberToRequestedBedroomsMap.end(),std::vector<int>());
continue;
}
int bedroomNumber;
lineStream >> bedroomNumber;
int studentNumber;
lineStream >> studentNumber;
if (studentNumber != 0) {
studentNumberToRequestedBedroomsMap[studentNumber-1].push_back(
bedroomNumber);
bedroomDemand[INDEX(bedroomNumber)]++;
} else {
// End of test case
// Sort bedRequested in order of least in-demand to most in-demand
for (auto &item : studentNumberToRequestedBedroomsMap) {
std::sort(
item.begin(), item.end(),
[&bedroomDemand](int bedroomNumberLeft, int bedroomNumberRight) {
return bedroomDemand[INDEX(bedroomNumberLeft)] <
bedroomDemand[INDEX(bedroomNumberRight)];
});
}
// Start assigning rooms to students starting with the least in-demand
// room requested.
for (auto item : studentNumberToRequestedBedroomsMap) {
for (auto bedroomNumber : item) {
auto result = assignedBedrooms.insert(bedroomNumber);
if (result.second) {
break;
}
}
}
std::cout << assignedBedrooms.size() << std::endl;
assignedBedrooms.clear();
bedroomDemand.clear();
studentNumberToRequestedBedroomsMap.clear();
}
}
}