upc 2020春季个人训练赛第九场
问题 A: 水题大战
题目描述
小Q最近正在给一个比赛出题目，他认为第一题应该是老少皆宜的。于是，他出了一个题目，然后让n个人来评价这个题目。
每个人会对这个题目做出评价，有难和简单两种，1表示难，0表示简单。如果所有人都认为这个题目简单，那么这个题目就是简单的，否则这个题目就是难的。
输入
输入第一行是一个正整数T，表示数据的组数。
接下来对于每组数据，先输入一个正整数n，表示参与评价的人的数量，接下来一行有n个整数，每个整数都是0或者1，表示对当前题目的评价。
输出
输出共T行，每行一个答案。如果该题简单，就输出EASY，否则输出HARD。
样例输入 Copy
2
3
0 0 1
1
0
样例输出 Copy
HARD
EASY
提示
样例共有2组数据：
第一组数据n是3,2个人认为是简单，1个人认为是难，所以是HARD。
第二组数据n是1，这唯一的一个人认为是简单的，所以是EASY。
对于40%的数据，T=1,1≤n≤5。
对于100%的数据，1≤T≤10,1≤n≤100。
思路：
简单的判断即可，只要出现1就输出HAND
int t,n,flag;
int a[105];
int main()
{
t = read();
while(t--)
{
n = read();
flag = 0;
for(int i=1;i<=n;i++) a[i] = read();
for(int i=1;i<=n;i++)
{
if(a[i] != 0) flag = 1;
}
if(flag) printf("HARD\n");
else printf("EASY\n");
}
return 0;
}
问题 B: 学生分组
题目描述
在小Q的大学里，有n个学生，其中n一定是偶数。每个学生有一定的编程能力，第i个学生的能力是ai。
学校里的老师希望把学生组成n/2个队伍， 每个队伍里面有2个学生，每个学生只能属于一个队伍。两个学生可以组队，当且仅当他们的能力是相同的，否则他们就不能理解对方。
由于开始的时候， 学生的能力参差不齐，可能无法顺利组队。但是学生可以通过做题来提高自己的能力，每做一题，能力就可以提高1 。
学校的老师希望计算出这些学生最少需要做多少题，才能顺利的组队。
输入
输入的第一行是一个正整数n，表示学生的数量，保证n一定是偶数。
接下来一行有n个正整数，第i个整数ai表示第i个学生当前的编程能力。
输出
输出只有一行一个整数，表示所有学生最少需要做的总题数，才能使得顺利组队。
样例输入 Copy
6
5 10 2 3 14 5
样例输出 Copy
5
提示
样例中，第3个人和第4个人组队，第1个人和第6个人组队，第2个人和第5个人组队，然后第3个人做1题，第2个人做4题，总共做5题，他们就能顺利组队了。
对于50%的数据，1≤n≤1000，所有学生的能力最多只有2种不同的取值。
对于100%的数据，1≤n≤100000，1≤ai≤100。
思路：
排序之后，每两个之间计算差即可
int n,ans;
int a[100007];
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
sort(a,a+n);
for(int i=1;i<n;i+=2)
ans += a[i]-a[i-1];
printf("%d",ans);
}
问题 C: 变换高度
题目描述
小Q是一个牛逼的少年，他段近无聊的在纸上画了n个塔.第i个塔的高度是hi。他会对塔进行一种操作，操作定义为在某个高度H的时候，如果第i个塔的高度高于H，我们必须把这个塔的高度变成H. 这样一次操作的代价是从所有塔里面移除的1×1方块的总和。如果一次操作的代价小于等于k，那么我们就称这个操作为友好操作（k≥n）。
现在请你计算最少需要多少次友好操作，才能使得所有的塔的高度都变成相同。显然，这个肯定有答案．下面图可以参考（样例1 ) :
输入
输入第－行是两个整数n和k， 表示塔的数量和操作相关的系数k。
第二行有n个空格隔开的整数h1,h2,…hn。
输出
输出只有一个整数，表示最少需要的友好操作的数量，使得每个塔的高度都相同。
样例输入 Copy
5 5
3 1 2 2 4
样例输出 Copy
2
提示
样例如图所示，需要2个友好操作，第1次设定H为2，代价为3，第2次设定H为1，代价为4。
对于50%的数据，1≤n≤2000，hi≤2000。
对于100%的数据，1≤n≤2×105，n≤k≤109，hi≤2×105。
int n,k,t,sum,ans;
int maxx = -1;
int minn = 999999999;
int a[maxn];
int main()
{
n = read();
cin >> k;
for(int i=0;i<n;i++)
{
cin >> t;
maxx = max(maxn,t);
minn = min(minn,t);
a[t]++;//记录当前高度的个数
}
for(int i=maxx;i>=minn;i--)
//从最高到最低枚举
{
if(a[i] == n)//当前所有高度已经相同
{
if(sum){
ans++; break;
}
}
if(sum+a[i] <= k){
sum += a[i];
}
else
{
ans++;
sum = 0;
if(sum+a[i] <= k){
sum += a[i];
}
}
a[i-1] += a[i];
a[i] = 0;
}
cout << ans << endl;
return 0;
}
问题 F: 交换位置
题目描述
农夫John确信快乐的奶牛能产出更多的牛奶，所以他在他的谷仓里装了一个巨大的迪斯科球，并打算教他的奶牛跳舞!
农夫John在看了很多流行的奶牛舞后，决定教他的奶牛跳“Bovine Shuffle"。“Bovine Shuffle"需要他的N只牛（1 ≤ N ≤ 100）按顺序排成一排，依次进行“
Shuffle(洗牌)”这个动作，也就是轮换位置排成不同的顺序。为了让奶牛更容易找到自己的位置，John为他的牛按1 … N的顺序排上了号，也就是说第一个奶牛是位置1，第二个是位置2，一直到最后一只是位置N。
每场Shuffle都是用N个数字从a1…aN来标明，换句话说，在这个过程中，原本位置在i的奶牛换到了位置ai (每一次的移动位置ai都在1…N的范围内).每头牛在Shuffle的过程中都会移动到它的新位置。幸运的是，所有这些移动位置ai都是清楚的，不会有两头奶牛跑去同一个位置上。
农场主John给每头奶牛都标上了7位整数位的ID编号。如果给你了3次洗牌后的奶牛编号顺序，请给出原本的奶牛顺序。
输入
第一行输入N代表了奶牛的总数。
下一行输入在a1至an间的整数之间的整数N。最后一行写三次洗牌后，N头奶牛的ID编号顺序。
输出
每一行写一头奶牛的ID号，共N行来标明3次洗牌前的奶牛顺序。
样例输入 Copy
5
1 3 4 5 2
1234567 2222222 3333333 4444444 5555555
样例输出 Copy
1234567
5555555
2222222
3333333
4444444
思路：
换的是位置，最后需要输出编号，所以定义一个结构体来存储编号和变量 i
题目给出了最后的编号，所以我们倒着推回去
1（1234567）
2（2222222）
3（3333333）
4（4444444）
5（5555555）
我们让v[i].num存储一开始的 i
即v[1].num = 1 , v[2].num = 2 , v[3].num = 3…
第一次洗牌
v[1].num = a[v[1].num] = 1
v[2].num = a[v[2].num] = 3
v[3].num = a[v[3].num] = 4
v[4].num = a[v[4].num] = 5
v[5].num = a[v[5].num] = 2
其实第一次洗完牌我们就发现了其中规律
每次通过a[i]来更新v[i].num序号的值
最后只需要按v[i].num的序号来输出即可
int n;
int a[105],b[105];
struct node
{
int num;
string s;
}v[105];
int main()
{
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> a[i];
v[i].num = i;
}
for(int i=1;i<=n;i++) cin >> v[i].s;
int m = 3;
while(m--)
{
for(int i=1;i<=n;i++)
v[i].num = a[v[i].num];
}
for(int i=1;i<=n;i++)
cout << v[v[i].num].s << endl;
return 0;
}
问题 G: 最近的大哥
题目描述
有N个蚂蚁兄弟从左到右排成一行，每个蚂蚁见到比自己岁数大的蚂蚁就称为大哥。现在每只蚂蚁都先左看，寻找最近的大哥。找不到时输出0。
请编一个程序，帮助蚂蚁们计算每只蚂蚁的最近大哥是哪个？
输入
第一行2个正整数：N，N的范围是[1…100000]。
第二行：N个正整数，表示每只蚂蚁的年龄，每个数的范围是[0…1,000,000,000]。
输出
一行，N个整数，表示相应蚂蚁的最近大哥的编号。编号从1到N。
样例输入 Copy
6
8 6 3 3 5 1
样例输出 Copy
0 1 2 2 2 5
思路：
暴力寻找就可以，一旦向前找到比当前数大的数就结束本次循环
int n;
struct node
{
int x,y,z;
}a[maxn];
int main()
{
n = read();
for(int i=1;i<=n;i++)
{
a[i].x = read();
a[i].y = i;
}
for(int i=1;i<=n;i++)
{
for(int j=i-1;j>=1;j--)
{
if(a[i].x < a[j].x)
{
a[i].z = a[j].y;
break;
}
else a[i].z = 0;
}
}
for(int i=1;i<=n;i++)
printf("%d ",a[i].z);
printf("\n");
return 0;
}