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

### 正文

#### 题目1

input 3 3 4 5 1 0 5 5 3 2

output 9 0 6

```int main(int argc, const char * argv[]) {
int a, b, c;
int t;
cin >> t;
while (t--) {
cin >> a >> b >> c;
int ans = min(c / 2, b);
cout << min((b - ans) / 2, a) * 3 + ans * 3 << endl;
}
return 0;
}```

#### 题目 2

```int main(int argc, const char * argv[]) {
int x, y;
cin >> x >> y;
while (x <= y) {
int ok = 1;
int a[10] = {0};
int tmp = x;
while (tmp) {
if (a[tmp % 10]) ok = 0;
a[tmp%10] = 1;
tmp /= 10;
}
if (ok) {
cout << x << endl;
return 0;
}
++x;
}
cout << -1 << endl;

return 0;
}```

#### 题目3

Examples input 3 1 2 3 output 0 input 4 1 1 2 2 output 2

```    map<int, int> h;
for (int i = 0; i < n; ++i) {
int t;
scanf("%d", &t);
if (!h[t]) {
h[t] = ++cnt;
}
a[i] = h[t];
}

int left = 0, right = n; // [left, right)
int ans = n - 1;
while (left < right) {
int mid = (left + right) / 2;
int ok = 0;
for (int k = 0; k < n; ++k) { //
if (check(n, k, k + mid)) {
ok = 1;
break;
}
}
if (ok) {
ans = mid;
right = mid;
}
else {
left = mid + 1;
}
}
cout << ans << endl;```

```int a[N];
int vis[N];
int cnt = 0;
// [l, r)
bool check(int n, int l, int r) {
memset(vis, 0, sizeof(vis));
for (int i = 0; i < l; ++i) {
if (!vis[a[i]]) {
vis[a[i]] = 1;
}
else {
return false;
}
}
for (int i = r; i < n; ++i) {
if (!vis[a[i]]) {
vis[a[i]] = 1;
}
else {
return false;
}
}
return true;
}

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

map<int, int> leftMap, rightMap, gapMap;
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
gapMap[a[i]] = i;
}

int leftDifMax = 0, rightDifMax = 0;
for (int i = 0; i < n; ++i) {
if (leftMap[a[i]]) {
break;
}
leftMap[a[i]] = 1;
leftDifMax = i;
}

for (int i = n - 1; i >= 0; --i) {
if (rightMap[a[i]]) {
break;
}
rightMap[a[i]] = 1;
rightDifMax = i;
}

int tmp = 0, ans = (n - rightDifMax);
for (int i = 0; i <= leftDifMax; ++i) {
tmp = max(tmp, gapMap[a[i]]);
int r = max(rightDifMax, tmp + 1);
ans = max(ans, i + 1 + (n - r));
}

cout << (n - ans) << endl;

return 0;
}```

#### 题目4

Examples input 4 4 3 5 1 2 1 4 10 11 9 11 9 2 5 4 3 3 7 9 4 9

⁣output ⁣2 4 0 3

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

int t;
cin >> t;
while (t--) {
lld n, x;
cin >> n >> x;

for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
sort(a, a + n);
lld sum = 0, ans = 0;
for (int i = n - 1; i >= 0; --i) {
if (sum + a[i] >= x * (ans + 1)) {
sum += a[i];
++ans;
}
else {
break;
}
}
cout << ans << endl;
}

return 0;
}```

#### 题目5

Examples input 1 3 7 15 2 14 5 3 ⁣output ⁣6

```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) {
scanf("%lld%lld", &a[i], &val[i]);
}

lld sum = max(0ll, a[0] - val[n - 1]);
for (int i = 1; i < n; ++i) {
sum = sum + max(0ll, a[i] - val[i - 1]);
}

lld ans = sum - max(0ll, a[0] - val[n - 1]) + a[0]; // 直接打死第0个
for (int i = 1; i < n; ++i) {
lld tmp = sum - max(0ll, a[i] - val[i - 1]) + a[i];
ans = min(ans, tmp);
}

cout << ans << endl;
}

return 0;
}```

0 条评论

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

LeetCode上的题目是大公司面试常见的算法题，今天的目标是拿下5道算法题： 题目1是基于链表的大数加法，既考察基本数据结构的了解，又考察在处理加法过程中的...

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

LeetCode上的题目是大公司面试常见的算法题，今天的目标是拿下5道算法题： 题目1是基于链表的大数加法，既考察基本数据结构的了解，又考察在处理加法过程中的边...

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

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

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

前言 比赛就在这周末，这篇是比赛前最后一篇训练总结。 正文 hdu 5980（简单题） 题目大意 一个32位的数字，每个bytes包括8bit，所以一个整...

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

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

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

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

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

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

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

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

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

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