一.木材加工
题解：
二分答案，左边0，右边可以为最长的木头，但我直接赋值了一个很大的值，进行二分，随后写个check;内部遍历木头截取为mid木块的个数，要是>=k，满足要求，还可以继续往后面找，因为它是要求最大每段木头的长度，直至左边加一小于右边，最后输出左边；
代码：
#include <iostream>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <cstdio>
#include <stack>
#include <queue>
#include<set>
#include <string>
using namespace std;using ll = long long;
using ull = unsigned long long;
#define up(i, h, n) for (int i = h; i <= n; i++)
#define down(i, h, n) for(int i = h; i >= n; i--)
#define wh(x) while(x--)
#define node struct node
#define it ::iterator
#define Ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
constexpr int MaxN = 200005;
constexpr int MaxM = 10005;
constexpr int mod = 1e9 + 7;
constexpr int inf = 0x7fffffff;ll n, k;
ll a[MaxN];bool check(ll x) { // 判断是否能切割出长度为x的k段木头ll sum = 0;up(i, 1, n) {sum += a[i] / x;}return sum >= k;
}
int main() {Ios;cin >> n >> k;up(i, 1, n) {cin >> a[i];}ll l = 0, r = inf;while (l + 1 < r) { // l+1 为了避免死循环ll mid = (l + r) / 2;if (check(mid)) l = mid;else r = mid;}cout << l << endl;return 0;
}二.并查集
题解：
这是并查集的模版，并查集就是利用一个数组来标记他们，看他们是否是一起；
代码：
#include <iostream>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <cstdio>
#include <stack>
#include <queue>
#include<set>
#include <string>
using namespace std;using ll = long long;
using ull = unsigned long long;
#define up(i, h, n) for (int i = h; i <= n; i++)
#define down(i, h, n) for(int i = h; i >= n; i--)
#define wh(x) while(x--)
#define node struct node
#define it ::iterator
#define Ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
constexpr int MaxN = 10005;
constexpr int MaxM = 100005;
constexpr int mod = 1e9 + 7;
constexpr int inf = 0x7fffffff;void slove() {}int f[MaxN];int find(int x) { // 寻找；return f[x] == x ? x : f[x] = find(f[x]);
}
int main() {Ios;/*int t;cin >> t;while (t--) {slove();}*/int n, m;cin >> n >> m;up(i, 1, n) f[i] = i; //初始化up(i, 1, m) {int z, x, y;cin >> z >> x >> y;if (z == 1) {f[find(y)] = find(x); // 合并}else if (find(x) == find(y)) {cout << "Y" << endl;}else {cout << "N" << endl;}}return 0;
}三、单源最短路径（弱化版）
题解：
模版题，用Dijkstra,但是我还是有点不理解Dijkstra;
代码：
#include <iostream>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <cstdio>
#include <stack>
#include <queue>
#include<set>
#include <string>
using namespace std;using ll = long long;
using ull = unsigned long long;
#define up(i, h, n) for (int i = h; i <= n; i++)
#define down(i, h, n) for(int i = h; i >= n; i--)
#define wh(x) while(x--)
#define node struct node
#define it ::iterator
#define Ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
constexpr int MaxN = 500005;
constexpr int MaxM = 10005;
constexpr int mod = 1e9 + 7;
constexpr int inf = 0x7fffffff;node{int to,w,next;
}e[MaxN];
int head[MaxM], dis[MaxM], book[MaxM];
int n, m, s;
int main() {Ios;cin >> n >> m >> s;book[s] = 1;memset(head, -1, sizeof(head));int num = 0;up(i, 1, m) {int u, v, w;cin >> u >> v >> w;e[num].to = v;e[num].w = w;e[num].next = head[u];head[u] = num++;}up(i, 1, n) {dis[i] = pow(2, 31) - 1;}for (int i = head[s]; i != -1; i = e[i].next) {dis[e[i].to] = min(e[i].w, dis[e[i].to]);}dis[s] = 0;up(i, 1, n) {int min1 = pow(2, 31) - 1;int k = s;up(j, 1, n) {if (!book[j] && dis[j] < min1) {min1 = dis[j];k = j;}}book[k] = 1;for (int j = head[k]; j != -1; j = e[j].next) {if (dis[e[j].to] > dis[k] + e[j].w) {dis[e[j].to] = dis[k] + e[j].w;}}}up(i, 1, n) {cout << dis[i] << ' ';}return 0;
}
