第一题 [USACO07DEC]Bookshelf B
题目描述
Farmer John最近为奶牛们的图书馆添置了一个巨大的书架，尽管它是如此的大，但它还是几乎瞬间就被各种各样的书塞满了。现在，只有书架的顶上还留有一点空间。
所有 N ( 1 ≤ N ≤ 20 , 000 ) 头奶牛都有一个确定的身高 H i ( 1 ≤ H i ≤ 10 , 000 )。设所有奶牛身高的和为S。书架的高度为B，并且保证 1 ≤ B ≤ S < 2 , 000 , 000 , 007。
为了够到比最高的那头奶牛还要高的书架顶，奶牛们不得不像演杂技一般，一头站在另一头的背上，叠成一座“奶牛塔”。当然，这个塔的高度，就是塔中所有奶牛的身高之和。为了往书架顶上放东西，所有奶牛的身高和必须不小于书架的高度。
显然，塔中的奶牛数目越多，整座塔就越不稳定，于是奶牛们希望在能够到书架顶的前提下，让塔中奶牛的数目尽量少。 现在，奶牛们找到了你，希望你帮她们计算这个最小的数目。
输入格式
第 1 行: 2 个用空格隔开的整数：N 和 B ；
第 2 … N + 1 行: 第 i + 1行是 1 个整数：H i 。
输出格式
第 1 行: 输出 1个整数，即最少要多少头奶牛叠成塔，才能够到书架顶部
样例 #1
样例输入 #1
6 40 6 18 11 13 19 11
样例输出 #1
3
提示
输入说明:
一共有 6头奶牛，书架的高度为 40，奶牛们的身高在 6 … 19之间。
输出说明:
一种只用 3 头奶牛就达到高度 40的方法：18 + 11 + 13 。当然还有其他方法，在此不一一列出了。
解题思路
1）输入数据进行排序
2）高度到达40退出循环，输出答案。
参考代码
#include<bits/stdc++.h> using namespace std; bool cmp(int a,int b){return a>b;} int a[100000],n,ans,H,s; int main() { cin>>n>>H; for(int k=0;k<n;k++) cin>>a[k]; sort(a,a+n,cmp); for(;s<H;ans++)s+=a[ans]; cout<<ans; }
第二题 车厢重组
题目描述
在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转 180度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。
输入格式
共两行。
第一行是车厢总数 N ( ≤ 10000 )。
第二行是 N个不同的数表示初始的车厢顺序。
输出格式
一个整数，最少的旋转次数。
样例 #1
样例输入 #1
4 4 3 2 1
样例输出 #1
6
解题思路
1）冒泡排序，记录交换次数。
2）输出答案。
参考代码
#include <bits/stdc++.h> using namespace std; int main() { int n; cin>>n; int a[10050]; for (int i=0;i<n;i++) { cin>>a[i]; } int ans=0; for (int j=0;j<n-1;j++) { for (int i=0;i<n-j-1;i++) { if (a[i]>a[i+1]) { swap(a[i],a[i+1]); ans++; } } } cout<<ans; return 0; }
第三题 欢乐的跳
题目描述
一个 n 个元素的整数数组，如果数组两个连续元素之间差的绝对值包括了 [ 1 , n − 1 ] 之间的所有整数，则称之符合“欢乐的跳”，如数组 { 1 , 4 , 2 , 3 } 符合“欢乐的跳”，因为差的绝对值分别为：3 , 2 , 1 。
给定一个数组，你的任务是判断该数组是否符合“欢乐的跳”。
输入格式
每组测试数据第一行以一个整数 n ( 1 ≤ n ≤ 1000 ) 开始，接下来 n个空格隔开的在
之间的整数。
输出格式
对于每组测试数据，输出一行若该数组符合“欢乐的跳”则输出 Jolly，否则输出 Not jolly。
样例 #1
样例输入 #1
4 1 4 2 3
样例输出 #1
Jolly
样例 #2
样例输入 #2
5 1 4 2 -1 6
样例输出 #2
Not jolly
提示
1 ≤ n ≤ 1000
解题思路
1）用数组记录下差，判断是否有n-1个数
2）输出答案。
参考代码
#include<bits/stdc++.h> using namespace std; int s[10000010],f[10000010],n,ans=0; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>s[i]; if(i!=1) { f[abs(s[i-1]-s[i])]++; } } for(int i=1;i<n;i++) { if(f[i]!=0) { ans++; } } if(ans==n-1) { cout<<"Jolly"; } else cout<<"Not jolly"; return 0; }
第四题 [NOIP2009 普及组] 分数线划定
题目描述
世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才，A 市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的 150 %划定，即如果计划录取 m名志愿者，则面试分数线为排名第 m × 150 %（向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。
现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成绩。
输入格式
第一行，两个整数 n , m ( 5 ≤ n ≤ 5000 , 3 ≤ m ≤ n )，中间用一个空格隔开，其中 n 表示报名参加笔试的选手总数，m表示计划录取的志愿者人数。输入数据保证 m × 150 % 向下取整后小于等于 n。
第二行到第 n + 1 行，每行包括两个整数，中间用一个空格隔开，分别是选手的报名号 k ( 1000 ≤ k ≤ 9999 )和该选手的笔试成绩 s ( 1 ≤ s ≤ 100 )。数据保证选手的报名号各不相同。
输出格式
第一行，有 2 个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为进入面试的选手的实际人数。
从第二行开始，每行包含 2个整数，中间用一个空格隔开，分别表示进入面试的选手的报名号和笔试成绩，按照笔试成绩从高到低输出，如果成绩相同，则按报名号由小到大的顺序输出。
样例 #1
样例输入 #1
6 3 1000 90 3239 88 2390 95 7231 84 1005 95 1001 88
样例输出 #1
88 5 1005 95 2390 95 1000 90 1001 88 3239 88
提示
【样例说明】
m × 150 % = 3 × 150 % = 4.5，向下取整后为 4。保证 4 个人进入面试的分数线为 88 ，但因为 88有重分，所以所有成绩大于等于 88的选手都可以进入面试，故最终有 5个人进入面试。
解题思路
1）记录所有人的成绩，排序。
2）符合条件的录入。
参考代码
#include<bits/stdc++.h> using namespace std; struct z { int num; int score; }a[5010]; int cmp (z n,z m) { if (n.score==m.score) return n.num<m.num; return n.score>m.score; } int main() { int n,m,q; cin>>n>>m; q=floor(m*1.50); for (int i=1;i<=n;++i) cin>>a[i].num>>a[i].score; sort(a+1,a+n+1,cmp); cout<<a[q].score<<" "; int i=q; while (a[i].score==a[i+1].score&&i<=n) i++; cout<<i<<endl; for (int j=1;j<=i;++j) cout<<a[j].num<<" "<<a[j].score<<endl; return 0; }
