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

正文

题目1

Examples input 2 2 1 output 2 1 样例解释： 对于样例1，当n=2的时候一共有2种染色方法：

```int main(int argc, const char * argv[]) {
// insert code here...

int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cout << n << endl;
}

return 0;
}```

题目2

Examples input 5 7 20 3 101 18 11 11 10 234 2 8 9 7 250 122 19 41 21 321 10 3 10 8 6 1

output Yes No Yes No Yes

```int main(int argc, const char * argv[]) {
// insert code here...

int t;
cin >> t;
while (t--) {
lld n, a, b, c, d;
cin >> n >> a >> b >> c >> d;
lld l = (c - d), r = (c + d);
lld ans = -1;
lld gapL = (a - b) * n, gapR = (a + b) * n;
bool ok = 0;;
if (gapL <= l && l <= gapR) {
ok = 1;
}
else if (gapL <= r && r <= gapR) {
ok = 1;
}
else if (l <= gapL && gapL <= r) {
ok = 1;
}
else if (l <= gapR && gapR <= r) {
ok = 1;
}
if (ok) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}

return 0;
}```

题目3

Examples input 2 6 5 -2 4 8 6 5 4 8 1 4 2 output 5 5 4 6 8 -2 1 2 4 8

```int a[N];
int ans[N];

int main(int argc, const char * argv[]) {
// insert code here...

int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) cin >>a[i];
sort(a, a + n);
int l = 0, r = n - 1, k = n - 1;
while (l <= r) {
ans[k--] = a[r--];
if (l <= r) {
ans[k--] = a[l++];
}
}
for (int i = 0; i < n; ++i) {
cout << ans[i] << " ";
}
cout << endl;
}

return 0;
}```

题目4

Examples input 2 8 6 1 2 4 1 2 4 1 2 5 3 3 2 3 2 1

output 3 2 2 2

```int a[N];
queue<int> q;

int main(int argc, const char * argv[]) {
// insert code here...

int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
while (!q.empty()) {
q.pop();
}

int ans = 0, start = 0;
for (int i = 1; i < n - 1; ++i) {
if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
q.push(i);
while (q.back() - q.front() + 2 >= k) {
q.pop();
}
if (q.size() > ans) {
ans = q.size();
start = q.back() + 1 - (k - 1);
}
}
}
cout << ans + 1 << " " << max(0, start) + 1 << endl;
}

return 0;
}```

题目5

Examples input 3 4 1 7 6 5 5 1 2 3 4 5 2 0 -4 output 2 0 3

```typedef long long lld;
lld p[N];
lld a[N];

bool check(int n, int k) {
lld last = llinf;
for (int i = n - 1; i >= 0; --i) {
lld tmp = a[i];
for (int j = k; j >= 1; --j) {
if (tmp + p[j-1] <= last) {
tmp += p[j - 1];
}
}
if (tmp > last) {
return false;
}
last = tmp;
}
return true;
}

int main(int argc, const char * argv[]) {
// insert code here...
p[0] = 1;
for (int i = 1; i < 31; ++i) p[i] = p[i-1] * 2;

int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
int k = 0;
while (1) {
if (check(n, k)) {
cout << k << endl;
break;
}
k++;
}
}

return 0;
}```

0 条评论

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

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

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

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

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

每个路口的机动车道有三个方向，分别是左转、直行、右转，同时路口有一条人行道； 每行输入有四个数字l，s，r，p，分别表示左转、直行、右转、人行道的交通信号灯是...

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

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

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

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

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

前言 这次的题目质量非常高，除了第一道签到题之外都是很不错的想法题，值得学习。 几乎所有的程序员都能做A题； 思维缜密的程序员可以做B题； 数学还没还给老师的能...

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

BAT常见的算法面试题解析： 程序员算法基础——动态规划 程序员算法基础——贪心算法 工作闲暇也会有在线分享，算法基础教程----腾讯课堂地址。

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

前言 转眼已经到5月，可是我还没订17年的计划，真是悲伤的故事。 今年还是想花点时间，玩玩题目。 题目不会太简单，也不会太难，简单的如1、2题，难的如3、...

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

题目链接 题目大意： 有一个由数字0、1组成的字符串，长度为n； 现在需要将其切分成若干段，要求每一段0和1的数量是不相同的。 比如说1, 101, 0...