程序员进阶之算法练习（四十五）
正文
题目1. Sagheer and Crossroads
题目链接 题目大意： 在一个十字路口（见图），一共有4个路口；
每个路口的机动车道有三个方向，分别是左转、直行、右转，同时路口有一条人行道； 每行输入有四个数字l，s，r，p，分别表示左转、直行、右转、人行道的交通信号灯是否亮起；
如果某个路口人行道的灯亮起，同时有机动车可以通过这个路口，那么会发生交通事故，输出"YES"； 如果所有的路口都不会发生交通事故，则输出"NO";
Examples input 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 output YES 样例解释： 路口1的人行道信号灯亮起的同时，路口1和4的机动车可以通过这个路口，会发生交通事故； 同时路口4的人行道信号灯亮起的同时，路口2、3的机动车可以通过路口4，会发生交通事故；
题目解析： 题意很清晰，分别判断每个路口是否有人行道信号灯亮起，如果有再判断是否有机动车通过。
int n = 4;
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) {
if (a[i][4] == 1) { // pedestrian light on
int l = i > 1 ? i - 1 : 4, r = i < 4 ? i + 1 : 1, s = i + 2 > 4 ? (i + 2) % 4 : i + 2;
if (a[l][3] || a[r][1] || a[s][2] || a[i][1] || a[i][2] || a[i][3]) {
cout << "YES" << endl;
return 0;
}
}
}
cout << "NO" << endl;题目2.Sagheer, the Hausmeister
题目链接 题目大意： 在一栋大厦里，有n层，每层有m个房间，同时每层的左右两侧都存在一个楼梯； 有些人晚上离开大厦没有关灯，小明是大厦的管理员，每天晚上需要把所有的房间的灯关掉； 输入n行数据，每行有m+2个数字，第一列和最后一列表示楼梯，第2列到第m+1列表示房间的灯（1表示亮着）； 小明一开始在最底层（第n行）左边的楼梯的位置，假设小明上一层楼梯的时间为1，经过一个房间的时间也为1，关灯的不耗费时间； 并且小明会把这一行的灯都关掉，再走到上一层。
问，小明最少需要多少时间，才能关掉所有的灯；
Example input 3 4 001000 000010 000010 output 12
题目解析： 典型的动态规划。 每一层的初始状态只有两种：最左或者最右。 走到上一层的时候，也只有最左和左右两个选择。 那么，一共有4种情况： 1、初始在最左，走完当前层，然后回到最左； 2、初始在最左，走完当前层，然后直接到最左； 3、初始在最右，走完当前层，然后回到最右； 4、初始在最右，走完当前层，然后直接到最左； 这也是四个状态转移方程。 第i层，我们用lMax[i]和rMax[i]来表示，这一层灯的最左边和最右边位置，这样可以快速算出走完当前层的代价。 详细代码转移见下面：（trick，可能某一层为全部为0）
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
for (int j = 1; j <= m; ++j) {
if (a[i][j] == '1') {
rMax[i] = j;
}
}
for (int j = m; j >= 1; --j) {
if (a[i][j] == '1') {
lMax[i] = m - j + 1;
}
}
}
dp[n + 1][0] = -1, dp[n + 1][1] = inf;
for (int i = n; i >= 1; --i) {
int upStep = 1;
// 1 从右到左，从左到左
dp[i][0] = dp[i + 1][1] + upStep + (m + 1);
dp[i][0] = min(dp[i][0], dp[i + 1][0] + upStep + rMax[i] * 2);
//
dp[i][1] = dp[i + 1][0] + upStep + (m + 1);
dp[i][1] = min(dp[i][1], dp[i + 1][1] + upStep + lMax[i] * 2);
}
int cur = 1;
while (cur < n && lMax[cur] == 0) { // 找到最后一层有灯的
++cur;
}
cout << min(dp[cur + 1][0] + rMax[cur] + 1, dp[cur + 1][1] + lMax[cur] + 1) << endl;题目3.Sagheer and Nubian Market
题目链接
题目大意：
小明到商店买东西，商店里有n个物品，小明带了总共s的钱；
每个商品有个基础的价格a[i]，同时商品还有一个附加价格：
当小明总共购买k个物品的时候，每个商品的价格=基础价格+附加价格=a[i]+i*k；
现在小明希望在总价格不超过s的前提下，尽可能买更多的物品； 如果物品一样多，小明希望总价格price尽可能的少；
输入数据 n and s (1 ≤ n ≤ 1e5 and 1 ≤ s ≤ 1e9) (1 ≤ ai ≤ 1e5) 输出数据 能买到物品数量和总价格price；
Examples input 3 11 2 3 5 output 2 11
样例解释： 样例中，小明无法购买3个物品，因为购买3个时，价格是 [5, 9, 14]，总价格是28； 如果购买2个物品，价格是 [4, 7, 11]，小明可以买前两个。
题目解析： 在不考虑附加价格的时候，可以直接对价格排序，从价格最小的物品开始，直到无法购买即可； 附加价格的影响是当购买的物品越多的时候，物品的的价格是越贵，这里是具有单调性的。 那么通过二分购买的数量mid，即可排除附加价格的影响。 每次得到二分的购买数量mid后，更新每个物品的价格，再排序进行求值。 总得复杂度是二分复杂度*排序复杂度=O(NlogNlogN);
lld n, s;
cin >> n >> s;
for (int i = 1; i <= n; ++i) {
scanf("%lld", &node[i]);
}
lld l = 0, r = n + 1, ans = 0, ansTotal = 0;
while (l < r) {
lld mid = (l + r) / 2;
if (mid == 0) {
break;
}
lld sum = 0;
for (int i = 1; i <= n; ++i) {
a[i] = node[i] + mid * i;
}
sort(a + 1, a + 1 + n);
for (int i = 1; i <= mid; ++i) {
sum += a[i];
}
if (sum > s) {
r = mid;
}
else {
ans = mid;
ansTotal = sum;
l = mid + 1;
}
}
cout << ans << " " << ansTotal << endl;题目4. Game of Credit Cards
题目链接 题目大意： 小明和小红各有n张卡片，每张卡片的数字是0~9； 现在小明和小红进行比赛，每次出一张卡片，每张卡片只能用一次，数字小的输； 现在问： 小红最少会输几次？还有小红最多能赢多少次？
输入数据： 第一行 数字n，表示卡片数量 (1 ≤ n ≤ 1000) 第二行 n个字符，0~9组成，表示小明的卡牌； 第三行 n个字符，0~9组成，小时小红的卡片；
输出数据： 第一行，一个整数，表示小红最少输次数；
Examples input 3 123 321 output 0 2 样例解释： 最少输的出牌顺序是小明vs小红 ： 123vs123； 最多赢的出牌顺序是小明vs小红 ： 123vs231;
题目解析： 分情况讨论，先看最少输的情况： 如果希望小红尽可能少输，那么应该让小红每个数字尽可能找大于等于小明的数字进行匹配； 于是可以采取这种的策略：对于每个数字，尽可能找与之最近的数字；
最多赢的情况： 如果希望小红尽可能多赢，那么应该让小红每个数字尽可能大于小明的数字进行匹配即可。
int n;
cin >> n;
cin >> a >> b;
int ansMin = 0;
for (int i = 0; i < n; ++i) {
int id = -1, dif = 100;
for (int j = 0; j < n; ++j) {
if (!vis[j] && b[i] >= a[j]) {
if (b[i] - a[j] < dif) {
id = j;
dif = b[i] - a[j];
}
}
}
if (id != -1) {
vis[id] = 1;
++ansMin;
}
}
int ansMax = 0;
memset(vis, 0, sizeof(vis));
for (int i = 0; i < n; ++i) {
int id = -1, dif = 100;
for (int j = 0; j < n; ++j) {
if (!vis[j] && b[i] > a[j]) {
if (b[i] - a[j] < dif) {
id = j;
dif = b[i] - a[j];
}
}
}
if (id != -1) {
vis[id] = 1;
++ansMax;
}
}
cout << n - ansMin << " " << ansMax << endl;题目5.Alyona and Spreadsheet
题目链接 题目大意： 给出n行数据，每行有m列，用a[i][j]来表示第i行，第j个数字； 我们说某一列（比如说第j列）是有序的，如果满足：对于所有的i，a[i][j] ≤ a[i+1][j]； 现在有k个询问，每个询问给出区间[l, r]，在第l行到第r行是否存在有序的列，有则输出Yes，无则输出No。
输入数据 n and m (1 ≤ n·m ≤ 100 000) a[i][j] (1 ≤ a[i][j] ≤ 1e9) k (1 ≤ k ≤ 100 000) l[i] and r[i] (1 ≤ l[i] ≤ r[i] ≤ n).
输出数据 有则输出Yes，无则输出No。
Example input 5 4 1 2 3 5 3 1 3 2 4 5 2 3 5 5 3 2 4 4 3 4 6 1 1 2 5 4 5 3 5 1 3 1 5 output Yes No Yes Yes Yes No
题目解析： 我们把每一列分成多个区间，每个区间内部都是有序的；（比如说样例的第一列1，3，4，5，4就可以分成两个区间[1, 4], [5, 5]) 对于询问[l, r]即是，是否存在一个有序的区间，覆盖给定的区间[l, r]； 这题目没有要求统计[l, r]内的有序区间数量，只是询问是否存在，那么可以采用一种特殊的优化方式： 对于两个区间[l, r]，我们直接用best[r]来表示r最多能达到r-l的距离； 每一个点保留能到达最远的距离，这样在询问的时候，就可以通过best[r]和(r-l)的大小，O(1)判断是否存在；
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
int x;
scanf("%d", &x);
a[i].push_back(x);
}
}
for (int j = 0; j < m; ++j) {
dp[j] = 1;
}
best[0] = 1;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (a[i][j] >= a[i - 1][j]) {
dp[j]++;
}
else {
dp[j] = 1;
}
best[i] = max(best[i], dp[j]);
}
}
int k;
cin >> k;
while (k--) {
int l, r;
cin >> l >> r;
--r, --l;
if (best[r] >= r - l + 1) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
}总结
题目1，简单的实现题； 题目2，动态规划，需要考虑边界情况，最容易被当成贪心； 题目3，题目看起来很复杂，用二分可以很容易解决； 题目4，分类讨论，各自用贪心解决； 题目5，先考虑暴力解法，然后发现有大量重复操作，增加预处理，问题解决；