会社の真題シリーズの滴滴_レストラン問題(欲張り)

3659 ワード

アルゴリズムとデータ構造

1、テーマの説明
あるレストランにはnつのテーブルがあり、各テーブルにはパラメータがあります.aが収容できる最大人数です.mロットのお客様がいて、各ロットのお客様には2つのパラメータがあります:b人数、c予想消費金額.スペルが許可されていない場合は、合計消費金額の最大入力説明:m+2行を含む入力を含むように、一部の顧客を選択するアルゴリズムを実装します.1行目の2つの整数n(1<=n<=50000)、m(1<=m<=50000)の2番目の動作n個のパラメータa、すなわち、各テーブルに収容可能な最大人数は、スペースで区切られ、範囲は32ビットintの範囲内である.次にm行、各行に2つのパラメータb,cを示す.第iロットのお客様の人数と予想消費金額をそれぞれ表し、スペースで区切られ、範囲は32ビットintの範囲内である.出力の説明:
最大の総予想消費金額を示す整数を出力
2、例
入力3 52 4 21 33 53 75 91 10出力
20
3、問題の解析
1)私の最初の考えは机の授業に収容された人数a[]を並べ替え、客pairを並べ替え、テーブルごとに人数が要求を満たす最大消費金額を選択し、もう一つの追加の配列flag[i]は第i陣の客が選択されたかどうかを記録した.この時間的複雑度はO(n*m)であり,問題で与えられた規模はタイムアウトに違いなく,テスト中に通過率は90%にすぎなかった.
最初のコードは次のとおりです.

#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
int main() {
	int n, m;
	cin >> n >> m;
	vector a(n);
	vector> cus(m);
	vectorflag(m,0);//flag[i]==0      ，flag==1       
	int i,j,pos=-1;
	ll max = 0, sum = 0;//max                  ，sum        
	for (i = 0; i < n; ++i) {
		cin >> a[i];
	}
	for (i = 0; i < m; ++i) {
		cin >> cus[i].first >> cus[i].second;
	}
	time_t start_time = clock();
	sort(a.begin(), a.end());
	sort(cus.begin(), cus.end());

	for (i = 0; i < n; ++i) {
		max = 0;
		pos = -1;
		for (j = 0; j max) {
					max = cus[j].second;
					if (pos != -1)
						flag[pos] = 0;//          ，         0
					flag[j] = 1;
					pos = j;
				}
			}//end else
		}//end for j
		//cout << "i=" << i << " pos="<

2)上の考え方は、テーブルごとに適切なお客様を見つけるために、他の人の考えを参考にして、お客様に消費金額の降順に並べ、テーブルも容量の降順に並べ、その後、お客様ごとに適切なテーブル(つまり、要求を満たす容量の最小のテーブルを見つける)を見つけるために、重要な一歩です.テーブルを見つけた後、テーブルの列から削除します.これにより、問題の規模が縮小しつつある.テーブルを探すときに二分法(?)を使うという考え方もあります.
次は、変更後のコードです.
いくつかのプログラミングの詳細に注意してください.
eraseメソッドを呼び出すときは、a.begin()+j-1が0より大きいこと、すなわちjが0より大きいことを保証します.次の行のコードは、この条件を保証します.

		if (cus[i].second > a[0])//             
			continue;

#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
int main() {
	int n, m;
	cin >> n >> m;
	vector a(n);
	vector> cus(m);//    ，  
	int i, j;
	ll max = 0, sum = 0;//max                  ，sum        
	for (i = 0; i < n; ++i) {
		cin >> a[i];
	}
	for (i = 0; i < m; ++i) {
		cin >> cus[i].second >> cus[i].first;
	}
	time_t start_time = clock();
	sort(a.begin(), a.end());
	reverse(a.begin(), a.end());//        
	sort(cus.begin(), cus.end());
	reverse(cus.begin(), cus.end());//        
	//          ，               
	for (i = 0; i < m; ++i) {
		if (n == 0)//         
			break;
		if (cus[i].second > a[0])//             
			continue;
		int j = 0;
		while (j < n&&a[j] >= cus[i].second)
			j++;//j-1              
		sum += cus[i].first;
		a.erase(a.begin() + j - 1);//         ，   j    0
		n--;//      1
	}
	
	cout << std::fixed;
	cout << sum << endl;
	time_t end_time = clock();
	cout << "    ：" << (double)(end_time - start_time) / CLOCKS_PER_SEC << "s" << endl;
}

チネル on EC2 フェイルオーバ (ENIなし)

Railsのsession_storeをRedisで設定している場合のWercker設定方法