私はここ数日、この座席割り当ての問題を理解しようとして頭がおかしくなり、誰かが私を助けてくれるかどうか疑問に思っていました.
指示は言う:
n 人の学生のグループが授業 (または映画) のために一緒に到着し、ちょうど n 席が連続して 1 列に空いていると仮定します。座席に関する m の好みが与えられた場合、その好みを満たすために何人の学生が着席できるかを決定する必要があります。
入力
入力はキーボードのみから行われます。入力は、複数のテスト ケースで構成されます。各テスト ケースは、0 < n および 0 ≤ m の 2 つの整数で始まります。ここで、n は着席する生徒の数、m は好みの数です。簡単にするために、生徒には 0 から n - 1 までの番号が付けられていると仮定します。その後、m 行が続き、それぞれが好みを記述します。行は、0 ≤ a < b < n および 0 < を満たす 3 つの整数 a、b、および c で構成されます。 |c| < n。c が正の場合、10 代の a と b は最大でも c 席離れて座りたいと考えます。c が負の場合、a と b は少なくとも -c 席離れて座りたいと考えます。入力の終了は、n = m = 0 で構成される行によって通知されます。
出力
各テスト ケースの出力は、すべての入力制約を満たすグループの可能な座席配置の数を含む 1 行です。
サンプル入力
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;
}
私はそれが不完全であることを知っていますが、主に設定の各行を正しい順列と比較して結果を数える方法を見つけようとして立ち往生しています。ユーザーが入力として入力したベクトル内の各要素の位置 (例: 例では 0,1) を取得し、見つかった各順列が 0 と 1 の間に少なくとも 2 席あるかどうかを確認することを考えました。しかし、それだけではうまくいきません。