1

この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();
    }
  }
}
4

0 に答える 0