算法训练.

一.奶牛晒衣服

题解：

这应该是个二分题，但是我用的是贪心暴力写的，思想就是循坏每次都让湿度最高的使用一次烘衣机，要是湿度最高的可以在自然条件下都能晒干就结束循环，这样内部我第一想法就是每次都排个降序；但是交上去发现后面数据超时了，也就是每次都排序太麻烦了，于是边思考到每次只需要把刚刚使用过烘衣机过后的湿度在插入进去，就只要一个for循环即可了这样就会快很多；随后也是AC了

代码：

#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 = 100005;
constexpr int mod = 1e9 + 7;
constexpr int inf = 0x7fffffff;


int s[MaxN];
int cmp(int a, int b) {
	return a > b;
}
int main() {

	Ios;
	int n, a, b;
	cin >> n >> a >> b;
	up(i, 1, n) {
		cin >> s[i];
	}
	sort(s + 1, s + n + 1, cmp);
	int ans = 0;
	while (true) {
		if (s[1] <= ans * a)break;
		s[1] -= b;
		int temp = s[1];
		int i;
		for (i = 2; s[i] > temp && i <= n; i++) {
			s[i - 1] = s[i];
		}
		s[i - 1] = temp;
		ans++;
	}
	cout << ans << endl;
}

二.进击的奶牛

题解：

这道题就是经典的二分了，首先这个牛棚得排个序，因为他输入的时候并不是有序输入的，排完序便可以二分了，对于这个二分的条件就是假设当前牛在这个牛棚，那么这头牛与前面那头牛的间距是否大于等于最大的最近距离，最后看牛是否都放入牛棚即可；

代码：

#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, m;
ll a[MaxN];

bool check(int x) {
	ll sum = 1;// 初始化为1
	int k = 0; // 将第一头牛放入
	up(i, 1, n - 1) {
		if (a[i] - a[k] >= x) {
			sum++;
			k = i;  // 满足要求放入
		}

	}
	return sum >= m; // 牛是否都放进去
}
int main() {

	Ios;
	cin >> n >> m;
	up(i, 0, n - 1) {
		cin >> a[i];
	}
	sort(a, a + n);
	ll l = 0,r=inf;
	while (l + 1 < r) {
		int  mid = (l + r) / 2;
		if (check(mid)) l = mid ;
		else r = mid ;
	}
	if (check(r)) cout << r << endl;
	else cout << l << endl;
	return 0;
}

三.最小生成树

题解：

这道题有两个算法：Kruskal和Prim,我用的是Kruskal，运用结构体将边的起点，终点，权值存起来，按照权值升序排序，建立并查集，并且初始化，随后循环将边加入值并查集，直至n-1即可，也是就五个顶点只需要四条边即可；

代码：

#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 = 50005;
constexpr int MaxM = 200005;
constexpr int mod = 1e9 + 7;
constexpr int inf = 0x7fffffff;


node{
	int x,y,z;
};
node a[MaxM];
int cmp(node a, node b) {
	return a.z < b.z;
}
int f[MaxN];

int find(int x) {
	return f[x] == x ? x : f[x] = find(f[x]);
}
int main() {

	Ios;
	int n, m;
	cin >> n >> m;
	up(i, 1, n) f[i] = i;
	up(i, 1, m) {
		cin >> a[i].x >> a[i].y >> a[i].z;
	}
	sort(a + 1, a + m + 1, cmp);
	int ans = 0;
	int num = 0;
	up(i, 1, m) {
		if (find(a[i].x) != find(a[i].y)) {
			f[find(a[i].y)] = f[a[i].x];
			ans += a[i].z;
			num++;
		}
		if (num == n - 1) {
			break;
		}
	}
	if (num == n - 1) cout << ans << endl;
	else cout << "orz" << endl;
	return 0;
}