第一题 [USACO07DEC]Bookshelf B

题目描述

Farmer John最近为奶牛们的图书馆添置了一个巨大的书架，尽管它是如此的大，但它还是几乎瞬间就被各种各样的书塞满了。现在，只有书架的顶上还留有一点空间。

所有 $N(1\le N\le 20,000)$ 头奶牛都有一个确定的身高 $H_i(1\le H_i\le 10,000)$。设所有奶牛身高的和为S。书架的高度为B，并且保证 $1\le B\le S<2,000,000,007$。

为了够到比最高的那头奶牛还要高的书架顶，奶牛们不得不像演杂技一般，一头站在另一头的背上，叠成一座“奶牛塔”。当然，这个塔的高度，就是塔中所有奶牛的身高之和。为了往书架顶上放东西，所有奶牛的身高和必须不小于书架的高度。

显然，塔中的奶牛数目越多，整座塔就越不稳定，于是奶牛们希望在能够到书架顶的前提下，让塔中奶牛的数目尽量少。 现在，奶牛们找到了你，希望你帮她们计算这个最小的数目。

输入格式

• 第 $1$ 行: 2 个用空格隔开的整数：$N$ 和 $B$；
• 第 $2\dots N+1$ 行: 第 $i+1$ 行是 $1$ 个整数：$H_i$。

输出格式

• 第 $1$ 行: 输出 $1$ 个整数，即最少要多少头奶牛叠成塔，才能够到书架顶部

样例 #1

样例输入 #1

6 40
6
18
11
13
19
11
1
2
3
4
5
6
7

样例输出 #1

3
1

提示

输入说明:

一共有 $6$ 头奶牛，书架的高度为 $40$，奶牛们的身高在 $6\dots 19$之间。

输出说明:

一种只用 $3$ 头奶牛就达到高度 $40$ 的方法：$18+11+13$。当然还有其他方法，在此不一一列出了。

解题思路

• 1）输入数据进行排序
• 2）高度到达40退出循环，输出答案。

参考代码

#include   
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;       
}
1
2
3
4
5
6
7
8
9
10
11
12

第二题 车厢重组

题目描述

在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转 $180$ 度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。

输入格式

共两行。

第一行是车厢总数 $N(\le 10000)$。

第二行是 $N$ 个不同的数表示初始的车厢顺序。

输出格式

一个整数，最少的旋转次数。

样例 #1

样例输入 #1

4
4 3 2 1
1
2

样例输出 #1

6
1

解题思路

• 1）冒泡排序，记录交换次数。
• 2）输出答案。

参考代码

#include 
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

第三题 欢乐的跳

题目描述

一个 $n$ 个元素的整数数组，如果数组两个连续元素之间差的绝对值包括了 $[1,n-1]$ 之间的所有整数，则称之符合“欢乐的跳”，如数组 { 1 , 4 , 2 , 3 } \{1,4,2,3\} {1,4,2,3} 符合“欢乐的跳”，因为差的绝对值分别为：$3,2,1$。

给定一个数组，你的任务是判断该数组是否符合“欢乐的跳”。

输入格式

每组测试数据第一行以一个整数 $n(1\le n\le 1000)$ 开始，接下来 $n$ 个空格隔开的在 $[-10^8,10^8]$ 之间的整数。

输出格式

对于每组测试数据，输出一行若该数组符合“欢乐的跳”则输出 Jolly，否则输出 Not jolly。

样例 #1

样例输入 #1

4 1 4 2 3
1

样例输出 #1

Jolly
1

样例 #2

样例输入 #2

5 1 4 2 -1 6
1

样例输出 #2

Not jolly
1

提示

$1\le n\le 1000$

解题思路

• 1）用数组记录下差，判断是否有n-1个数
• 2）输出答案。

参考代码

#include 
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

第四题 [NOIP2009 普及组] 分数线划定

题目描述

世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才，A 市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的 $150\%$ 划定，即如果计划录取 $m$ 名志愿者，则面试分数线为排名第 $m\times 150\%$（向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。

现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成绩。

输入格式

第一行，两个整数 $n,m(5\le n\le 5000,3\le m\le n)$，中间用一个空格隔开，其中 $n$ 表示报名参加笔试的选手总数，$m$ 表示计划录取的志愿者人数。输入数据保证 $m\times 150\%$ 向下取整后小于等于 $n$。

第二行到第 $n+1$ 行，每行包括两个整数，中间用一个空格隔开，分别是选手的报名号 $k(1000\le k\le 9999)$和该选手的笔试成绩 $s(1\le s\le 100)$。数据保证选手的报名号各不相同。

输出格式

第一行，有 $2$ 个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为进入面试的选手的实际人数。

从第二行开始，每行包含 $2$ 个整数，中间用一个空格隔开，分别表示进入面试的选手的报名号和笔试成绩，按照笔试成绩从高到低输出，如果成绩相同，则按报名号由小到大的顺序输出。

样例 #1

样例输入 #1

6 3 
1000 90 
3239 88 
2390 95 
7231 84 
1005 95 
1001 88
1
2
3
4
5
6
7

样例输出 #1

88 5 
1005 95 
2390 95 
1000 90 
1001 88 
3239 88
1
2
3
4
5
6

提示

【样例说明】

$m\times 150\%=3\times 150\%=4.5$，向下取整后为 $4$。保证 $4$ 个人进入面试的分数线为 $88$，但因为 $88$ 有重分，所以所有成绩大于等于 $88$ 的选手都可以进入面试，故最终有 $5$ 个人进入面试。

解题思路

• 1）记录所有人的成绩，排序。
• 2）符合条件的录入。

参考代码

#include 
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28