Level3题目整理

L3-001 凑零钱

按从大到小排序，可以实现大的覆盖小的

#include<bits/stdc++.h>
using namespace std;
queue<int> q;
const int N = 1e4 + 10;
int n,m;
int v[N];
int dp[N];
//bool vis[N][110];
pair<int, int> pre[N][110];
bool cmp(int a,int b) {return a > b;
}int main() {cin >> n >> m;for(int i = 1; i <= n; i++) {cin >> v[i];}sort(v + 1, v + 1 + n,cmp);for(int i = 1; i <= n; i++) {for(int j = m; j >= v[i]; j--) {
//			dp[j] = max(dp[j],dp[j - v[i]] + v[i]);if(dp[j] <= dp[j-v[i]] + v[i]) {dp[j] = dp[j-v[i]] + v[i];pre[i][j] = make_pair(i-1, j-v[i]);
//				vis[i][j] = true;} else {pre[i][j] = make_pair(i-1, j);}}}if(dp[m] == m) {pair<int, int> p = make_pair(n, m);while (p.first != 0) {int x = pre[p.first][p.second].first;int y = pre[p.first][p.second].second;if (y != p.second) {if (p.second != m) cout << ' ';cout << v[p.first];}p = make_pair(x, y);}} else {cout << "No Solution";}
}

暴力解法：（👍👍👍）
也可以过很多，先排个序，优先全选最小的，所以只要存在第一种方案即是最优的

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int n,m;
int v[N];
int path[N];
int idx;
bool vis[N];
bool ok = false;
void dfs(int u,int sum) {if(u > n || sum > m) {return;}if(sum == m) {ok = true;int ct = 0;for(int i = 1; i <= n; i++) {if(vis[i]) {if(ct != 0) {cout << " ";}cout << v[i];ct++;}}exit(0);}vis[u] = true;dfs(u + 1,sum + v[u]);vis[u] = false;dfs(u + 1,sum);}
int main() {cin >> n >> m;for(int i = 1; i <= n; i++) {cin >> v[i];}sort(v+1,v+1+n);dfs(0,0);cout << "No Solution";}

L3-002 特殊堆栈

法一：暴力模拟过程（会TLE）

需要注意在peekMedian时，进行排序时，我们不能对进行模拟的数组直接进行排序，这样排序后会影响后续操作，我们应该再开一个辅助数组进行进行排序和输出。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int st[N];
int cst[N];
int idx;
int main() {int n;cin >> n;for(int i = 1; i <= n; i++) {string op;int x;cin >> op;if(op == "Pop") {if(idx <= 0) {cout << "Invalid" << endl;} else {cout << st[idx] << endl;--idx;}} else if(op == "Push") {cin >> x;st[++idx] = x;} else {if(idx == 0) {cout << "Invalid" << endl;} else {for(int i = 1; i <= idx; i++){cst[i] = st[i];}sort(cst+1,cst+1+idx);if(idx % 2 == 0){cout << cst[idx/2] << endl;}else{cout << cst[idx/2 + 1] << endl;}}}}
}

法二：采用vector顺序插入，lower_bound(),

#include<bits/stdc++.h>
using namespace std;
vector<int> num ;
stack<int> st ;
vector<int>::iterator it;
int main() {int n;cin >> n;for(int i = 1; i <= n; i++) {string op;int x;cin >> op;if(op == "Pop") {if(num.size() == 0) {cout << "Invalid" << endl;} else {cout << st.top() << endl;it = lower_bound(num.begin(),num.end(),st.top());num.erase(it);st.pop();}} else if(op == "Push") {cin >> x;it = lower_bound(num.begin(),num.end(),x);num.insert(it,x);st.push(x);} else {if(num.size() == 0) {cout << "Invalid" << endl;} else {int t = 0;if(num.size()%2 == 0) {t = num.size()/2;} else {t = (num.size() + 1) / 2;}cout << num[t - 1] << endl;}}}
}

L3-004 肿瘤诊断(三维bfs)

法1：dfs(有两个点过不了，估计是递归太深)

#include<bits/stdc++.h>
using namespace std;
int idx;
int dx[6] = {0,0,-1,1,0,0};
int dy[6] = {-1,1,0,0,0,0};
int dz[6] = {0,0,0,0,-1,1};int a[80][1300][150];
bool vis[80][1300][150];int ans;
int cnt;
int m,n,l,t;
bool check(int z,int x,int y) {if(x >= 1 && x <= m && y >= 1 && y <= n && z >= 1 && z <= l && a[z][x][y] == 1 && !vis[z][x][y]){return true;}return false;
}
void dfs(int z,int x,int y) {for(int k = 0; k <= 5; k++) {int nx = x + dx[k];int ny = y + dy[k];int nz = z + dz[k];if(check(nz,nx,ny)) {cnt++;vis[nz][nx][ny] = true;dfs(nz,nx,ny);}}
}int main() {cin >> m >> n >> l >> t;for(int z = 1; z <= l; z++) {for(int x = 1; x <= m; x++) {for(int y = 1; y <= n; y++) {cin >> a[z][x][y];}}}for(int z = 1; z <= l; z++) {for(int x = 1; x <= m; x++) {for(int y = 1; y <= n; y++) {if(!vis[z][x][y] && a[z][x][y] == 1) {cnt = 1;vis[z][x][y] = true;dfs(z,x,y);if(cnt >= t)ans += cnt;}}}}cout << ans;
}

法2：三维bfs

#include<bits/stdc++.h>
using namespace std;
int idx;
int dx[6] = {0,0,-1,1,0,0};
int dy[6] = {-1,1,0,0,0,0};
int dz[6] = {0,0,0,0,-1,1};int a[80][1300][150];
bool vis[80][1300][150];int ans;
int cnt;
int m,n,l,t;
struct node {int z,x,y;
};
queue<node> q;
bool check(int z,int x,int y) {if(x >= 1 && x <= m && y >= 1 && y <= n && z >= 1 && z <= l && a[z][x][y] == 1 && !vis[z][x][y]) {return true;}return false;
}
void bfs(int z,int x,int y) {node t = {z,x,y};q.push(t);while(!q.empty()) {node cur = q.front();int z = cur.z;int x = cur.x;int y = cur.y;q.pop();cnt++;for(int k = 0; k <= 5; k++) {int nx = x + dx[k];int ny = y + dy[k];int nz = z + dz[k];if(check(nz,nx,ny)) {vis[nz][nx][ny] = true;node temp = {nz,nx,ny};q.push(temp);}}}}int main() {cin >> m >> n >> l >> t;for(int z = 1; z <= l; z++) {for(int x = 1; x <= m; x++) {for(int y = 1; y <= n; y++) {cin >> a[z][x][y];}}}for(int z = 1; z <= l; z++) {for(int x = 1; x <= m; x++) {for(int y = 1; y <= n; y++) {if(!vis[z][x][y] && a[z][x][y] == 1) {cnt = 0;vis[z][x][y] = 1;bfs(z,x,y);if(cnt >= t)ans += cnt;}}}}cout << ans;
}

L3-005 垃圾箱分布（多次dijkstra）

思路：以垃圾桶为源点分别进行dijkstra，存下来可行的答案，排序输出即可
需要处理：因为垃圾桶为G1-Gm所以我们将垃圾桶映射到n+1到n+m即可
（1）需要注意每次选取的最小值应该是!vis[i]
（2）每次都需要进行初始化

坐标映射：

int isP(string x) {int index;if(x[0] == 'G') {index = n +  stoi(x.substr(1));} else {index = stoi(x);}return index;
}

#include<bits/stdc++.h>using namespace std;
const int N = 1e3 + 200;
const int Inf = 1e9;
int a[N][N];
bool vis[N];
int dis[N];
int n,m,k,ds;struct node {int id;double minn;double ave;
} p[N];bool cmp(node a,node b) {if(a.minn == b.minn) {if(fabs(a.ave - b.ave) <= 1e-8) {return a.id < b.id;} else {return a.ave < b.ave;}}else{return a.minn > b.minn;}}
int idx;
void dijkstra(int s) {for(int i = 1; i <= m + n; i++) {vis[i] = false;dis[i] = Inf;}dis[s] = 0;for(int i = 1; i <= m + n; i++) {int mini = -1;int minn = Inf;for(int j = 1; j <= m + n; j++) {if(!vis[j] && dis[j] < minn) {minn = dis[j];mini = j;}}if(mini == -1) {break;}vis[mini] = true;for(int j = 1; j <= m + n; j++) {if(!vis[j] && dis[j] > dis[mini] + a[mini][j]) {dis[j] = dis[mini] + a[mini][j];}}}int midis = Inf;bool ok = true;double sum = 0;for(int i = 1; i <= n; i++) {
//		cout << dis[i] << endl;midis = min(midis,dis[i]);if(dis[i] > ds) {ok = false;break;}sum += dis[i];}if(ok) {p[++idx] = {s - n,midis,sum/n};}}void init() {for(int i = 1; i < N; i++) {for(int j = 1; j < N; j++) {if(i != j) {a[i][j] = Inf;}}}
}int isP(string x) {int index;if(x[0] == 'G') {index = n +  stoi(x.substr(1));} else {index = stoi(x);}return index;
}void read() {string p1,p2;int dist;cin >> p1 >> p2 >> dist;int x = isP(p1);int y = isP(p2);a[x][y] = a[y][x] = dist;
}
int main() {cin >> n >> m >> k >> ds;init();for(int i = 1; i <= k; i++) {read();}for(int i = n + 1; i <= n + m; i++) {dijkstra(i);}if(idx == 0) {cout << "No Solution";} else {sort(p + 1,p + 1 + idx,cmp);cout << "G" << p[1].id << endl;printf("%.1f %.1f",p[1].minn,p[1].ave);}}