贪心（6）其他贪心问题CSU 1410: 整数转换
目录一，其他贪心问题
二，OJ实战
CSU 1410: 整数转换
CSU 1588: 合并果子
HDU - 1257 最少拦截系统
HDU 5835 Danganronpa
一，其他贪心问题
除了排序、选取、背包三大类贪心问题之外，其他的都被归纳到本文。
二，OJ实战
CSU 1410: 整数转换
题目：
Description
我们可以通过对一个整数 A 进行加1操作或者乘2操作使其转换为另一个整数 B 。
给出两个整数 X , Y ，计算至少需要多少步才能将 X 转换为 Y 。 .
Input
输入的第一行包含一个整数 T (1 ≤ T ≤ 5 00 )，表示一共有 T 组测试数据。
每组测试数据占一行，包含两个整数 X , Y (1 ≤ X ≤ Y ≤ 10 18 )。
Output
对于每组测试数据，输出至少需要多少步才能将 X 转换为 Y 。
Sample Input
3
1 1
3 10
2 11
Sample Output
0
3
4
代码：
#include<iostream>
using namespace std;
int main()
{
int t;
long long x, y;
cin >> t;
while (t--)
{
cin >> x >> y;
long long ans = 0;
while (y > x)
{
if (y < x * 2)
{
ans += y - x;
break;
}
if (y % 2 == 0)y /= 2;
else y--;
ans++;
}
cout << ans << endl;
}
return 0;
}
CSU 1588: 合并果子
题目：
Description
现在有n堆果子，第i堆有ai个果子。现在要把这些果子合并成一堆，每次合并的代价是两堆果子的总果子数。求合并所有果子的最小代价。
Input
第一行包含一个整数T（T<=50），表示数据组数。
每组数据第一行包含一个整数n（2<=n<=1000），表示果子的堆数。
第二行包含n个正整数ai（ai<=100），表示每堆果子的果子数。
Output
每组数据仅一行，表示最小合并代价。
Sample Input
2
4
1 2 3 4
5
3 5 2 1 4
Sample Output
19
33
如果只能合并相邻的那就是区间DP，参考 CSU - 1592 石子归并 javascript:void(0)
本题是贪心，每次选取最小的2个合并，和哈夫曼编码差不多
代码：
#include<iostream>
#include<queue>
using namespace std;
int main()
{
int t, n, num;
priority_queue<int>q;
cin >> t;
while (t--)
{
while (!q.empty())q.pop();
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> num;
q.push(-num);
}
int ans = 0, a, b;
while (q.size() > 1)
{
a = q.top();
q.pop();
b = q.top();
q.pop();
ans += a + b;
q.push(a + b);
}
cout << -ans << endl;
}
return 0;
}
HDU - 1257 最少拦截系统
题目：
Description
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.
Input
输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)
Output
对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.
Sample Input
8 389 207 155 300 299 170 158 65
Sample Output
2
这是一个贪心的问题。
贪心策略：每次选择一个系统来拦截炮弹的时候，选择可以满足条件的所有系统中，高度最小的系统。
也就是尽量减小浪费的意思。
代码：
#include<iostream>
using namespace std;
int l;
int main()
{
int n, k, sum;
while (cin >> n)
{
for (int i = 0; i < 30000; i++)l = 30001;
while (n--)
{
cin >> k;
for (int i = 0; i < 30000; i++)if (l >= k)
{
l = k;
break;
}
}
sum = 0;
for (int i = 0; i < 30000; i++)sum += (l < 30001);
cout << sum << endl;
}
return 0;
}
HDU 5835 Danganronpa
题目：
Description
Chisa Yukizome works as a teacher in the school. She prepares many gifts, which consist of kinds with quantities of each kind, for her students and wants to hold a class meeting. Because of the busy work, she gives her gifts to the monitor, Chiaki Nanami. Due to the strange design of the school, the students' desks are in a row. Chiaki Nanami wants to arrange gifts like this:
1. Each table will be prepared for a mysterious gift and an ordinary gift.
2. In order to reflect the Chisa Yukizome's generosity, the kinds of the ordinary gift on the adjacent table must be different.
3. There are no limits for the mysterious gift.
4. The gift must be placed continuously.
She wants to know how many students can get gifts in accordance with her idea at most (Suppose the number of students are infinite). As the most important people of her, you are easy to solve it, aren't you?
Input
The first line of input contains an integer indicating the number of test cases.
Each case contains one integer . The next line contains numbers: , .
Output
For each test case, output one line containing “Case #x: y” (without quotes) , where x is the test case number (starting from 1) and y is the answer of Chiaki Nanami's question.
Sample Input
1
2
3 2
Sample Output
Case #1: 2
这个题目的意思是给出若干个数，比如本题2个数：3,2
每个数代表1种不同的球的个数，现在问你，最多能选出多少个，使得他们可以排成一排，相邻的球都不同。
比如本题，3个a，2个b可以排成ababa，答案应该是5。
但是本题有个限制，不想细说，总之就是如果这么算出来超过了sum的一半，那么答案就是sum的一半。
sum就是这若干个数的和，max就是这若干个数的最大值。
对于一般的若干个数，能如上排成一排其实就等价于max<=sum-max+1
也就是说，对于2,3,6，max=6,sum=11,刚好满足max=sum-max+1，那么2个a，3个b，6个c可以排成cacacbcbcbc
对于2,3,7，max=7,sum=12,不满足max<=sum-max+1,那么它们无论怎么排，都不满足条件。
所以现在就是要求，对于输入的若干个数，每个数可以变成不超过它的另外一个整数，
最后需要满足max<=sum-max+1，求sum的最大值。
其实这个问题很好求解，可以理解为贪心（真的是有够贪心）
首先排序，增序，然后前面所有的数都不变，最后一个数在满足max<=sum-max+1的情况下尽可能取最大。
就这样，没了，是的，没了。
代码：
#include<iostream>
#include<algorithm>
using namespace std;
int list;
int main()
{
int t, n, sum, s;
cin >> t;
for (int i = 1; i <= t;i++)
{
cin >> n;
sum = 0;
for (int i = 0; i < n; i++)
{
cin >> list;
sum += list;
}
sum /= 2;
sort(list, list + n);
s = 0;
for (int i = 0; i < n - 1; i++)s += list;
if (list <= s + 1)s += list;
else s += s + 1;
if (s>sum)s = sum;
printf("Case #%d: %d\n", i, s);
}
return 0;
}
https://blog.51cto.com/u_15458280/4846547
页:
[1]