贝壳找房4月12日算法笔试题AC代码(1,2,3)

#include <iostream>
#include <vector>
using namespace std;

bool cmp(vector<int>& a, int l, int r){
        // 通过比较函数来确定加入新队列的元素
	while (l < r){
		if (a[l] < a[r]) return true;
		else if (a[l] == a[r]) { ++l; --r; }
		else return false;
	}
	return true;
}

int main(){
	int n; cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}

	vector<int> v;
	int i = 0, j = n - 1;
	while (i <= j){
		if (cmp(a, i, j)) v.push_back(a[i++]);
		else v.push_back(a[j--]);
	}

	for (int k = 0; k < n; k++){
		cout << v[k];
	}
	cout << endl;

	return 0;
}    

#include <iostream>
#include <vector>
using namespace std;

const int INF = 1000000000;

struct ListNode{
	int val;
	ListNode *prev, *next;
	ListNode(int x) : val(x), prev(NULL), next(NULL) {}
	ListNode(int x, ListNode* p, ListNode* q) :
		val(x), pre***ext(q) {}
};

void constructList(ListNode* head, int n){
	ListNode* p = head;
	int x;
	for (int i = 0; i < n; i++){
		scanf("%d", &x);
		p->next = new ListNode(x, p, NULL);
		p = p->next;
	}
}

void run(ListNode* head){
	ListNode *p;
	int mx = INF;
	for (p = head->next; p != NULL; p = p->next){
		if (p->val < mx){
			printf("%d ", p->val);
			mx = p->val;
			p->prev->next = p->next;
			if (p->next != NULL){
				p->next->prev = p->prev;
			}
		}
	}
	printf("\n");
}

int main(){
	int n; scanf("%d", &n);
	ListNode* head = new ListNode(0);
	constructList(head, n);
	while (head->next != NULL){
		run(head);
	}

	return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int ans = 100;
vector<int> order;

int n, m;
vector<int> a;
vector<vector<int>> b;

bool check(vector<int>& sum){
	for (int i = 0; i < n; i++){
		if (sum[i] < a[i]) return false;
	}
	return true;
}

void dfs(vector<int>& sum, vector<int>& arr, int cnt, int cur){
	if (check(sum) && cnt < ans){
		ans = cnt;
		order.clear();
		order.assign(arr.begin(), arr.end());
		return;
	}
	if (cur == m) return;
	// chose b[cur]
	for (int i = 0; i < n; i++){
		sum[i] += b[cur][i];
	}
	arr.push_back(cur + 1);
	dfs(sum, arr, cnt + 1, cur + 1);
	arr.pop_back();
	for (int i = 0; i < n; i++){
		sum[i] -= b[cur][i];
	}
	//abandon b[cur]
	dfs(sum, arr, cnt, cur + 1);
}

int main(){
	cin >> n;
	a.resize(n);
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}
	cin >> m;
	b.resize(m, vector<int>(n));
	for (int i = 0; i < m; i++){
		for (int j = 0; j < n; j++){
			cin >> b[i][j];
		}
	}

	vector<int> sum(n), arr;
	dfs(sum, arr, 0, 0);

	cout << ans << endl;
	for (int x : order) cout << x << ' ';
	cout << endl;

	return 0;
}