1. P1781 宇宙总统（字符串排序）

题意：

共有 nnn​ 个人竞选总统，给定每个候选人的票数，票数最多的人当选总统，输出候选人的编号和票数。

注：票数很大，可能会到 100100100 位数字。

思路：

将票数用 字符串 来存储，用结构体来存储每个人的票数和编号。

最后按照票数排序，输出最大的票数及对应的编号即可。

代码：

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