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;
}