C++电影座位

Question

这几天我一直在发疯，试图解决这个座位分配问题，想知道是否有人可以帮助我。

说明说:

假设一组 n 名学生一起来上课(或看电影)，并且在 1 行中连续有 n 个座位可用。给定 m 个座位偏好，你要确定学生有多少个座位可以满足偏好。

输入

输入将仅来自键盘。输入将包含多个测试用例。每个测试用例都以两个整数 0 < n 和 0 ≤ m 开头，其中 n 是要就座的学生人数，m 是偏好数。为简单起见，假设学生编号从 0 到 n - 1。然后是 m 行，每行描述一个偏好，其中一行由三个整数 a、b 和 c 组成，满足 0 ≤ a < b < n 和 0 < |c| < 名词。如果 c 是正数，那么青少年 a 和 b 最多想分开坐 c 个座位。如果 c 是负数，那么 a 和 b 至少要分开 -c 个座位。输入结束由 n = m = 0 组成的行表示。

输出

每个测试用例的输出是一行，其中包含满足所有输入约束的可能的座位安排数量。

示例输入

3 1

0 1 -2

3 0

0 0

示例输出

2

6

#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
#include <iterator>

using namespace std;


struct Preference
{
int a;
int b;                     //Struct with three preferences
int c;
};


int main()
{
int a,b,c,students,numpref;
int count = 0;

vector<Preference> prefs;              //Vector with struct to store preferences
Preference case1;

cout<<"Enter number of students and preferences: ";
cin>>students>>numpref;          //Total Number of students and preferences are entered



for(int i = 0; i<=numpref; i++)
{
cin>>case1.a>>case1.b>>case1.c;
prefs.push_back(case1);                  //Stores preferences in vector
cout<<endl;
}

vector<int> v2(a);               //Second vector created to store list of students

sort(v2.begin(), v2.end());

while(next_permutation(v2.begin(), v2.end()))  
                                  //Finds all permutations of student seating
{


}


system("PAUSE");
return 0;
}

我知道它不完整，但我主要是想弄清楚如何将每一行偏好与正确的排列进行比较，然后计算结果。我考虑过将用户输入的 vector 中每个元素的位置作为输入(例如:示例中的 0,1)并检查找到的每个排列是否在 0 和 1 之间至少有 2 个席位。但这行不通。

Answer 1

你认为的算法可以工作，但是很慢。我在您不完整的代码中发现了一些错误。

for(int i = 0; i<=numpref; i++) 

我觉得应该是这样

for(int i = 0; i<numpref; i++)