526互联

3.2 排序 参考代码

发布时间 2023-07-28 10:58:49作者: RonChen

P1059 [NOIP2006 普及组] 明明的随机数

  • 计数排序
#include <cstdio>
int a[1005];
int main()
{
	int n, cnt = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int x; scanf("%d", &x);
		if (a[x] == 0) { // 这个数没出现过（第一次出现）
			a[x] = 1; cnt++;
		}
	}
	printf("%d\n", cnt);
	for (int i = 1; i <= 1000; i++) 
		if (a[i] == 1) printf("%d ", i);
	return 0;
}

P2676 [USACO07DEC] Bookshelf B

#include <cstdio>
#include <algorithm>
using namespace std;
int h[20005];
int main()
{
    int n, b;
    scanf("%d%d", &n, &b);
    for (int i = 0; i < n; ++i) scanf("%d", &h[i]);
    sort(h, h + n);
    for (int i = n - 1; i >= 0; --i) {
        b -= h[i];
        if (b <= 0) { // 达到高度了就提前结束
            printf("%d\n", n - i);
            break;
        }
    }
    return 0;
}
  • 思路：尽量使用高的奶牛来叠，因此需要先对数据排序

P1152 欢乐的跳

  • 先把差求出来，再排序，分别和 1 ~ n-1 比较
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN = 1005;
int a[MAXN], d[MAXN];
int main()
{
	int n; scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 1; i < n; i++) d[i] = abs(a[i + 1] - a[i]);
	sort(d + 1, d + n);
	bool ok = true;
	for (int i = 1; i < n; i++)
		if (d[i] != i) {
			ok = false; break;
		}
	printf("%s\n", ok ? "Jolly" : "Not jolly");
	return 0;
}

P1271 [深基9.例1] 选举学生会

  • 计数排序
#include <cstdio>
int cnt[1000];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) {
        int x;
        scanf("%d", &x);
        ++cnt[x]; // 记录x出现的次数
    }
    for (int i = 1; i <= n; ++i)
        if (cnt[i] != 0) 
            for (int j = 0; j < cnt[i]; ++j) // 根据x出现的次数输出对应个数的x
                printf("%d ", i);
    return 0;
}

P1093 [NOIP2007 普及组] 奖学金

#include <cstdio>
#include <algorithm>
using namespace std;
struct Stu {
    int ch, math, eng, idx;
};
Stu s[305];
bool cmp(const Stu &s1, const Stu &s2) {
    int sum1 = s1.ch + s1.math + s1.eng;
    int sum2 = s2.ch + s2.math + s2.eng;
    if (sum1 != sum2) return sum1 > sum2;
    if (s1.ch != s2.ch) return s1.ch > s2.ch;
    return s1.idx < s2.idx;
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d%d", &s[i].ch, &s[i].math, &s[i].eng);
        s[i].idx = i + 1; // 学生编号
    }
    sort(s, s + n, cmp);
    for (int i = 0; i < min(5, n); ++i) 
        printf("%d %d\n", s[i].idx, s[i].ch + s[i].math + s[i].eng);
    return 0;
}

P1781 宇宙总统

#include <iostream>
#include <string>
using namespace std;
string s;
bool cmp(string &s1, string &s2) {
	if (s1.length() != s2.length()) return s1.length() > s2.length();
	else return s1 > s2;
}
int main()
{
	int n;
	cin >> n;
	string ans; 
	int id = 0;
	for (int i = 1; i <= n; i++) {
		cin >> s;
		if (cmp(s, ans)) {
			ans = s; 
			id = i; // 记录总统的号码
		}
	}
	cout << id << "\n" << ans << "\n";	
	return 0;
}

P1068 分数线划定

#include <cstdio>
#include <algorithm>
using namespace std;
struct Volunteer {
    int k, s;
};
Volunteer v[5005];
bool cmp(const Volunteer& v1, const Volunteer& v2) {
    if (v1.s != v2.s) return v1.s > v2.s;
    return v1.k < v2.k;
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d%d", &v[i].k, &v[i].s);
    sort(v + 1, v + n + 1, cmp); // 排序
    m = min(m * 3 / 2, n); // 整型之间的除法天然就是下取整
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (v[i].s >= v[m].s) ++cnt; // v[m].s为分数线
            else break;
    }
    printf("%d %d\n", v[m].s, cnt);
    for (int i = 1; i <= cnt; ++i) printf("%d %d\n", v[i].k, v[i].s);
    return 0;
}

P5143 攀爬者

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
struct Coordinate {
    int x, y, z;
};
bool cmp(const Coordinate &c1, const Coordinate &c2) {
    return c1.z < c2.z;
}
Coordinate a[50005];
double distance(const Coordinate &c1, const Coordinate &c2) {
    return sqrt((c1.x - c2.x) * (c1.x - c2.x) + (c1.y - c2.y) * (c1.y - c2.y) + (c1.z - c2.z) * (c1.z - c2.z));
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
    sort(a, a + n, cmp);
    double ans = 0;
    for (int i = 1; i < n; ++i) ans += distance(a[i - 1], a[i]);
    printf("%.3f\n", ans);
    return 0;
}

P1104 生日

#include <cstdio>
#include <algorithm>
using namespace std;
struct Stu {
    int y, m, d, idx;
    char s[25];
};
Stu stu[105];
bool cmp(const Stu& s1, const Stu& s2) {
    if (s1.y != s2.y) return s1.y < s2.y; // 出生年份不相等直接按照年份从小到大
    if (s1.m != s2.m) return s1.m < s2.m; // 年份相等月份不相等
    if (s1.d != s2.d) return s1.d < s2.d; // 同年同月不同日
    return s1.idx > s2.idx; // 同年同月同日生，把后输入的排前面
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%s%d%d%d", stu[i].s, &stu[i].y, &stu[i].m, &stu[i].d);
        stu[i].idx = i; // 记录输入顺序
    }
    sort(stu, stu + n, cmp);
    for (int i = 0; i < n; ++i) printf("%s\n", stu[i].s);
    return 0;
}

P1012 [NOIP1998 提高组] 拼数

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string a[25];
bool cmp(const string& s1, const string& s2) {
    return s1 + s2 > s2 + s1;
}
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a, a + n, cmp);
    for (int i = 0; i < n; ++i) cout << a[i];
    cout << endl;
    return 0;
}

排序策略的证明：考虑两个字符串 A 和 B
如果我们把字符串对应的十进制数看成 a 和 b，则 \(\overline{AB} > \overline{BA}\) 等价于
\(a \times 10^{\lvert B \rvert} + b > b \times 10^{|A|} + a\) 等价于
\(\frac{a}{10^{\lvert A \rvert}-1} > \frac{b}{10^{\lvert B \rvert}-1}\) 其中 |A| 和 |B| 代表字符串的长度
这说明这种比较策略具备传递性：即如果 AB 这种拼数方式优于 BA，BC 优于 CB，则最终顺序应为 ABC

P1204 [USACO1.2] 挤牛奶 Milking Cows

#include <cstdio>
#include <algorithm>
using namespace std;
struct Work {
    int l, r;
};
Work a[5005];
bool cmp(Work a, Work b) {
    return a.l < b.l;
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &a[i].l, &a[i].r);
    }
    sort(a, a + n, cmp);
    int bg = a[0].l, ed = a[0].r;
    int ans1 = ed - bg, ans2 = 0;
    for (int i = 1; i < n; i++) {
        if (a[i].l <= ed) {
            ed = max(ed, a[i].r);
            ans1 = max(ans1, ed - bg);
        } else {
            ans2 = max(ans2, a[i].l - ed);
            bg = a[i].l; ed = a[i].r;
            ans1 = max(ans1, ed - bg);
        }
    }
    printf("%d %d\n", ans1, ans2);
    return 0;
}