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;
}
#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;
}
#include<iostream>
using namespace std;
int l[30000];
int main()
{
int n, k, sum;
while (cin >> n)
{
for (int i = 0; i < 30000; i++)l[i] = 30001;
while (n--)
{
cin >> k;
for (int i = 0; i < 30000; i++)if (l[i] >= k)
{
l[i] = k;
break;
}
}
sum = 0;
for (int i = 0; i < 30000; i++)sum += (l[i] < 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[10];
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[i];
sum += list[i];
}
sum /= 2;
sort(list, list + n);
s = 0;
for (int i = 0; i < n - 1; i++)s += list[i];
if (list[n-1] <= s + 1)s += list[n-1];
else s += s + 1;
if (s>sum)s = sum;
printf("Case #%d: %d\n", i, s);
}
return 0;
}
开发技术
发布于：2021-12-27 10:58
|
阅读数：365
|
评论：0
QQ好友和群
QQ空间
