算法训练.

一.奶牛晒衣服

题解：

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

四.Minimum Glutton

题意：给你N盘菜肴，每盘菜肴有甜度和咸度两个属性；你可以将这些菜肴给他们任意排序，然后按顺序吃掉，但是当甜度超过X或者咸度超过Y时，就不能吃了；

题解：

题目要求的事最少吃几盘，那就将咸度和甜度两个都排降序，然后看两个分别能吃多少盘，然后取两个当中的min即可；

代码:

#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  x, y;
int n;
int cmp(int a, int b) {
	return a > b;
}
int main() {
 
	Ios;
	cin >> n >> x >> y;
	vector< int> a(n);
	vector< int> b(n);
	up(i, 0, n - 1) {
		cin >> a[i];
	}
	up(i, 0, n - 1) {
		cin >> b[i];
	}
	sort(a.begin(), a.end(),cmp);
	sort(b.begin(), b.end(), cmp);
	int ans = n;
	up(i, 0, n - 1) {
		x -= a[i];
		if (x < 0) {
			ans = min(ans, i + 1);
			break;
		}
	}
	up(i, 0, n - 1) {
		y -= b[i];
		if (y < 0) {
			ans = min(ans, i + 1);
			break;
		}
	}
	cout << ans << endl;
	return 0;
}

五.Grid Walk

题意：给你一个长为H，宽为W的一张图，然后图中有若干个障碍物，人物不能穿过障碍物和边界；给你起始位置，和一些指令，求经过这些指令后人物的位置；

题解：

简单的模拟题，就是L是左，R是右，U是上，D是下，模拟判断是否为边界和障碍物即可，若是到了边界或者障碍物就不动，否则就动；

代码：

#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;
 
int H, W;
int x, y;
 
int main() {
 
	Ios;
	cin >> H >> W;
	cin >> x >> y;
	x--; y--;
	vector<string> a(H);
	up(i, 0, H-1) {
		cin >> a[i];
	}
	string s;
	cin >> s;
	for (auto c : s) {
 
	if (c == 'L' && y - 1 >= 0 && a[x][y - 1] != '#') {
			y--;
		}
		if (c == 'R' && y + 1 < W && a[x][y + 1] != '#') {
			y++;
		}
		if (c == 'U' && x - 1 >= 0 && a[x - 1][y] != '#') {
			x--;
		}
		if (c == 'D' && x + 1 < H && a[x + 1][y] != '#') {
			x++;
		}
	}
	cout << x + 1 << ' ' << y + 1 << endl;
	
	return 0;
}