8.2排序专题总结

很不温馨提醒：本文章不是文章。

这篇文章也是非常的水好吧。

sort排序：

1. sort排序默认从小到大。

具体用法：

sort(a+1,a+n+1);

🍬纵介：

P9517 drink(题目作者：NaOH_Frog 题目难度：入门)：

1. ❌原因：不知道。
2. ❌代码：I don’t know.
3. 烧烤只是玷：区间。
4. ✔️袋吗：

#include<bits/stdc++.h>
using namespace std;
int main(){
	
	int n;
	cin >> n;
	int l = n+1,r = 0; //l定义成最大值,r定义成最小值。
	for (int i = 1;i <= n;i++){
		int x;
		cin >> x;
		if (x == 1){ //判断瓶子里是否有水。
			l = min(l,i); //有就取出l和i的最小值。
			r = max(r,i); //有就取出r和l的最大值。
		}
	}
	if (l == n+1 && r == 0){
		cout << "0" << endl; //如果l和r的值不变，就输出0。
	}else {
		cout << r-l+1; //否则输出r减去l加上1的值。
	}
	
	return 0;
}
//盲猜老师肯定说为什么这样。

P1639 [USACO18FEB] Teleportation B(题目作者：览遍千秋 题目难度：入门 题目翻译：传送)：

1. ❌原因：I don’t know.
2. ❌代码：我怎么知道。
3. 靠查值是点：贪心。
4. ✔️代码：

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main(){
	
	int a,b,x,y;
	cin >> a >> b >> x >> y;
	if (a > b){
		swap(a,b); //如果a大于b，就交换a和b的值。
	}
	if (x > y){
		swap(x,y); //如果x大于y，就交换x和y的值。
	}
	cout << min(abs(a-x)+abs(b-y),b-a); //输出abs(a-x)+abs(b-y)和b-a的最小值。
	
	return 0;
}
//盲猜老师会说为什么这样做。

P2356 弹珠游戏(题目作者：MedalPluS 题目难度：入门)：

1. ❌原因：没想到死暴力。
2. ❌代码：不知道。
3. 尻×☞⑩damn：死暴力。
4. ✔️代码：

#include<bits/stdc++.h>
using namespace std;
int a[10005][10005];
int main(){
	
	int n,sum=0,m=0;
	cin >> n;
	for (int i = 1;i <= n;i++){
		for (int j = 1;j <= n;j++){
			cin >> a[i][j];
		}
	}
	for (int i = 1;i <= n;i++){
		for (int j = 1;j <= n;j++){
			if (a[i][j] == 0){ //判断该位置是否有人。
				sum = 0; //sum初始化。
				for (int k = 1;k <= n;k++){
					sum += a[i][k]; //加上纵坐标上的分。
				}
				for (int k = 1;k <= n;k++){
					sum += a[k][j]; //加上横坐标上的分。
				}
				m = max(m,sum); //m和sum取最大值。
			}
		}
	}
	cout << m;
	
	return 0; //华丽结束。
}
//没写Bad Game也能✔️，只能说数据太水了。

B4239 [海淀区小学组 2025] 拜访朋友(题目作者：chen_zhe 题目难度：普及-)：

1. ❌原因：没看题。
2. ❌代码：没有。
3. 考察知识点：排序。
4. ✔️代码：

#include<bits/stdc++.h>
using namespace std;
int x[1000005];
int main(){
	
	int n,x0,sum,cnt;
	cin >> n >> x0;
	for (int i = 1;i <= n;i++){
		cin >> x[i];
	}
	sort(x+1,x+n+1);
    if (n == 1){
        cout << "0";
        return 0;
    }
	if (x0 <= x[1]){
		cout << x[n-1]-x0;
	}else if(x0 >= x[n]){
		cout << x0-x[2];
	}else {
		sum = min(x[n]-x0+x[n]-x[2],x[n-1]-x0+x[n-1]-x[1]);
		cnt = min(x0-x[1]+x[n-1]-x[1],x0-x[2]+x[n]-x[2]);
		cout << min(sum,cnt);
	}
	
	return 0;
}
//看不懂。

P1842 [USACO05NOV] 奶牛玩杂技(题目作者：JOHNKRAM 题目难度：普及/提高-)：

1. ❌原因：yellow题不会写。
2. ❌代码：不会就肯定没有。
3. 考察知识点：结构体。
4. ✔️代码：

#include<bits/stdc++.h>
using namespace std;
struct node{
    long long w,s;
}s[1000005];
bool cmp(node a,node b){
    return a.w+a.s<b.w+b.s;
}
int main(){
	
	long long n,ans=LONG_LONG_MIN,sum=0;
	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> s[i].w >> s[i].s;
	}
	sort(s+1,s+n+1,cmp);
	for (int i = 1;i <= n;i++){
		ans = max(ans,sum-s[i].s); //取ans和sum-s[i].s的最大值。
		sum += s[i].w;
	}
	cout << ans;
	
	return 0;
}
//盲猜老师肯定说为什么这么做。

P1090 [NOIP 2004 提高组] 合并果子(题目作者：CCF_NOI 题目难度：普及/提高-)：

1. ❌原因：新芝士点我怎么知道。
2. ❌代码：木有。
3. 考察知识点：不知道。
4. ✔️代码：

//待写

没有屎减不想写了。