# 程序员进阶之算法练习（四十五）

### 正文

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

Example input 3 4 001000 000010 000010 output 12

```   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

Examples input 3 11 2 3 5 output 2 11

```    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

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

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

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

0 条评论

• ### 程序员进阶之算法练习（四十四）

题目链接 题目大意： 给出整数x，求两个整数a和b，满足： ???(?,?)+???(?,?)=? . GCD是最大公约数； LCM是最小公约数；

• ### 程序员进阶之算法练习（十五）

前言 有朋友推荐一个新的算法练习网站leetcode，说北美的公司招人都是400题起步，国内公司招聘也经常用到，上海的尤其多。 很有意思，可以花点时间做做le...

• ### 程序员进阶之算法练习（十四）

前言 坚持做算法练习对开发的好处是抽象能力变强，拿到一个需求能很快对其进行抽象，然后再用学过的设计模式相关知识进行整理，最后用代码实现。 最大的好处在于：对...

• ### 程序员进阶之算法练习（二十五）

前言 算法题是锻炼思维的好工具，在解决问题的层面考察思考能力。 正文 1. Compote 题目链接 题目大意： 给出a、b、c三种材料，可以1:2:4组成...

• ### 程序员进阶之算法练习（五十三）

题目链接 题目大意： 有三堆石头，分别有a、b、c个； 现在可以执行操作： 1、从第一堆拿出1个石头，第二堆拿出2个石头； 2、从第二堆拿出1个石头，...

• ### 程序员进阶之算法练习（五十二）

题目链接 题目大意： n个人参加比赛，每个人都有一个分数a[i]，现在需要给这些人发奖牌（每个人最多发一个），要求：

• ### 程序员进阶之算法练习（五十一）

输入： 第一行，整数?表示有t个样例数量 (1≤?≤1000) 接下来每个样例一行，整数? (1≤?≤10^9).

• ### 程序员进阶之算法练习（二十四）

前言 已经有三个月未更新算法文章，大厂工作环境是步步紧逼的，使得所有的人越来越忙碌。余下的学习时间，要用于技术预研、知识面开阔、底层原理理解等等，慢慢算法只能占...

• ### 程序员进阶之算法练习（四十二）

题目链接 题目大意： n个学生参加测试，一共有m道题，每道题的答案可能是(A, B, C, D , E)中的一个； m道题分别有?1,?2,…,??，共m...