这几天我一直在发疯,试图解决这个座位分配问题,想知道是否有人可以帮助我。
说明说:
假设一组 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 个席位。但这行不通。
最佳答案
你认为的算法可以工作,但是很慢。我在您不完整的代码中发现了一些错误。
for(int i = 0; i<=numpref; i++)
我觉得应该是这样
for(int i = 0; i<numpref; i++)
关于C++电影座位,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12559021/