注 : 本贴子中的图片来自 https://www.nowcoder.com/discuss/638546?type=post&order=create&pos=&page=1&channel=-1&source_id=search_post_nctrack
1. 给定整数数组 A(A 中元素取值 0~9), 每次从 A 的首部或尾部选择一个数加入新的队列直到 A 为空, 问新的队列组成的数(从左往右看)最小是多少(可以包含前导 0)
#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;
} 2. 
用双向链表进行模拟
#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;
} 3. 
标准的回溯算法。由于要输出最终字典序最小的方案, 用一个数组来记录。
#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;
} 4. 不会做，也没想到方法。
全部评论
(0) 回帖