1. P1781 宇宙总统(字符串排序)
题意:
共有 nnn 个人竞选总统,给定每个候选人的票数,票数最多的人当选总统,输出候选人的编号和票数。
注:票数很大,可能会到 100100100 位数字。
思路:
将票数用 字符串 来存储,用结构体来存储每个人的票数和编号。
最后按照票数排序,输出最大的票数及对应的编号即可。
代码:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 30;struct node
{string x;int idx;
} a[N];bool cmp(node a, node b)
{if (a.x.size() != b.x.size())return a.x.size() > b.x.size();return a.x > b.x;
}int main()
{int n;cin >> n;for (int i = 1; i <= n; i++){cin >> a[i].x;a[i].idx = i;}sort(a + 1, a + 1 + n, cmp);cout << a[1].idx << endl;cout << a[1].x << endl;return 0;
}
2. P1223 排队接水(贪心)
题意:
有 nnn 个人在一个水龙头前排队接水,每个人接水的时间为 tit_iti 。
请找出这 nnn 个人排队的最优顺序,使得 nnn 个人的平均等待时间最小。
思路:
要想平均等待时间最小,那么就要每个人的等待时间都尽可能的短。
贪心的想,就要安排接水时间短的人在前面,这样后面人的等待时间就会尽量的短。
用 结构体 来存储每个人的接水时间和编号,当轮到这个人打水的时候,他的等待时间就是前面所有人接水时间的总和,相加后最后除以总人数,取小数点后两位输出即可。
代码:
#include <iostream>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
const int N = 1e6 + 10;struct node
{int t;int id;
} a[N];bool cmp(node x, node y)
{return x.t < y.t;
}int main()
{int n;cin >> n;for (int i = 1; i <= n; i++){cin >> a[i].t;a[i].id = i;}sort(a + 1, a + 1 + n, cmp);ll sum = 0;for (int i = 1; i <= n; i++){cout << a[i].id << " ";sum += a[n - i].t * i;}printf("\n%.2f\n", (double)sum / n);return 0;
}
3. P3817 小A的糖果(枚举 +贪心)
题意:
有 nnn 个糖果盒,每个糖果盒都有糖果。
现要求任意两个相邻的盒子中糖果的个数之和都不大于 xxx 。
问至少要取出多少颗糖果。
思路:
枚举
对于每个盒子,先判断是否大于 xxx ,先把超过的部分去掉;
再加上前面的盒子,如果总和超过 xxx ,再在当前盒子中取出超过的部分。
因为第一步操作保证了前面的盒子中糖果不超过 xxx 个,即前面都是合法的,所以我们只需要对后面的盒子进行操作就可以了。
代码:
#include <iostream>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
const int N = 1e5 + 10;int a[N];int main()
{int n, x;cin >> n >> x;for (int i = 0; i < n; i++)cin >> a[i];ll ans = 0;for (int i = 0; i < n; i++){if (a[i] > x){ans += (a[i] - x);a[i] = x;}ll sum = a[i] + a[i - 1];if (sum > x){ans += (sum - x);a[i] -= (sum - x);}}cout << ans << endl;return 0;
}
4. P1007 独木桥(思维)
题意:
一群士兵在独木桥上,独木桥十分狭窄,只能容纳 111 个人通行。假如有 222 个人相向而行在桥上相遇,那么他们 222 个人将无法绕过对方,只能有 111 个人回头下桥,让另一个人先通过。
每个士兵都有一个初始方向,均匀速行走,如果两个士兵相遇就会分别转身继续行走,转身不需要时间。
给定独木桥的长度为 LLL 。所有士兵速度都为 111 ,当士兵走到坐标为 000 或 L+1L + 1L+1 的位置就离开了独木桥。
士兵人数为 NNN ,然后 NNN 个整数分别代表每个士兵的初始坐标。
求所有士兵离开独木桥的最短和最长时间。
思路:
想象一下,不考虑谁是谁,当两个士兵相遇,可以视为他们 “穿过” 了对方继续行走,不影响最后的结果。
那么我们就可以依次对每个士兵进行判断,设当前坐标为 ppp ,有两种选择:
- 向左,需要 ppp 时间
- 向右,需要 L−p+1L - p + 1L−p+1 时间
分别取 maxmaxmax 和 minminmin ,每次比较判断最短和最长时间即可。
代码:
#include <iostream>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;int main()
{int l, n;cin >> l >> n;int mx = 0, mn = 0;for (int i = 1; i <= n; i++){int p;cin >> p;mx = max(mx, max(p, l - p + 1));mn = max(mn, min(p, l - p + 1));}cout << mn << ' ' << mx << endl;return 0;
}