首页 > 代码库 > noi题库(noi.openjudge.cn) 1.9编程基础之顺序查找T06——T15

noi题库(noi.openjudge.cn) 1.9编程基础之顺序查找T06——T15

T06 笨小猴

描述

笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用这种方法去选择选项的时候选对的几率非常大!

这种方法的具体描述如下:假设maxn是单词中出现次数最多的字母的出现次数,minn是单词中出现次数最少的字母的出现次数,如果maxn-minn是一个质数,那么笨小猴就认为这是个Lucky Word,这样的单词很可能就是正确的答案。

输入

只有一行,是一个单词,其中只可能出现小写字母,并且长度小于100。

输出

共两行,第一行是一个字符串,假设输入的的单词是Lucky Word,那么输出“Lucky Word”,否则输出“No Answer”;
第二行是一个整数,如果输入单词是Lucky Word,输出maxn-minn的值,否则输出0。

技术分享
样例输入
样例 #1:
error

样例 #2:
olympic
样例输出
样例 #1:
Lucky Word
2

样例 #2:
No Answer
0
样例

本题原来提示中的第二行有错误。

统计所有的字符出现的次数,sort排序,第一个非0的元素是最小值,第26个是最大值,然后判断是否为质数,注意0和1要特判

技术分享
 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 int a[30];
 6 char b[101];
 7 int main()
 8 {
 9     cin>>b; 
10     for(int i=0;i<strlen(b);i++)
11      a[b[i]-96]++;
12     sort(a+1,a+27);
13     int k;
14     for(int i=1;i<=26;i++)
15      if(a[i]!=0) 
16      {
17           k=a[i];
18           break;
19      }
20     int c=a[26]-k;
21     if(c==1||c==0)
22     {
23         cout<<"No Answer"<<endl<<0;
24         return 0;
25     }
26     for(int i=2;i*i<=c;i++)
27      if(c%i==0) 
28      {
29          cout<<"No Answer"<<endl<<0;
30          return 0;
31      }
32     cout<<"Lucky Word"<<endl<<c;
33 }
View Code

07:不与最大数相同的数字之和

描述

输出一个整数数列中不与最大数相同的数字之和。

输入

输入分为两行:
第一行为N(N为接下来数的个数,N <= 100);
第二行为N个整数,数与数之间以一个空格分开,每个整数的范围是-1000,000到1000,000。

输出

输出为N个数中除去最大数其余数字之和。

 

技术分享
样例输入
3
1 2 3 
样例输出
3
样例

 

在读入时记录最大值,还要记录有几个,最后用n个数的和减去

技术分享
 1 #include<iostream>
 2 using namespace std;
 3 int sum,maxx,m;
 4 int main()
 5 {
 6     int n,x;
 7     cin>>n;
 8     for(int i=1;i<=n;i++)
 9     {
10         cin>>x;
11         sum+=x;
12         if(x>maxx) maxx=x,m=1;
13         else if(x==maxx) m++;//前面有else,不用担心最大值在if加了一次,在这儿又加了一次
14     }
15     cout<<sum-m*maxx;
16 }
View Code

T08 白细胞计数

描述

医院采样了某临床病例治疗期间的白细胞数量样本n份,用于分析某种新抗生素对该病例的治疗效果。为了降低分析误差,要先从这n份样本中去除一个数值最大的 样本和一个数值最小的样本,然后将剩余n-2个有效样本的平均值作为分析指标。同时,为了观察该抗生素的疗效是否稳定,还要给出该平均值的误差,即所有有 效样本(即不包括已扣除的两个样本)与该平均值之差的绝对值的最大值。 
现在请你编写程序,根据提供的n个样本值,计算出该病例的平均白细胞数量和对应的误差。

输入

输入的第一行是一个正整数n(2 < n <= 300),表明共有n个样本。
以下共有n行,每行为一个浮点数,为对应的白细胞数量,其单位为10^9/L。数与数之间以一个空格分开。

输出

输出为两个浮点数,中间以一个空格分开。分别为平均白细胞数量和对应的误差,单位也是10^9/L。计算结果需保留到小数点后2位。

技术分享
样例输入
5
12.0
13.0
11.0
9.0
10.0
样例输出
11.00 1.00
样例

注意计算最大误差时,不要直接如果是最大值或最小值就排除,有可能出现两个相同的最值,应该保留一个

技术分享
 1 #include<iostream>
 2 #include<cmath>
 3 #include<algorithm>
 4 #include<cstdio>
 5 using namespace std;
 6 bool ok1,ok2;
 7 double a[1001];
 8 double minn=0x7fffffff,maxx,sum;
 9 double ans;
10 int main()
11 {
12     int n;
13     double x;
14     cin>>n;
15     for(int i=1;i<=n;i++)
16     {
17         cin>>x;
18         a[i]=x;        
19         sum+=x;
20         if(x>maxx) maxx=x;
21         if(x<minn) minn=x;
22     }
23     double m=(sum-maxx-minn)/(n-2);
24     printf("%.2lf",m);
25     printf(" ");
26     for(int i=1;i<=n;i++)
27     {
28         if(a[i]==minn&&!ok1) //只continue掉一个极值
29         { 
30              ok1=true;continue;
31         }
32         if(a[i]==maxx&&!ok2) 
33         {
34              ok2=true;continue;
35         }
36         ans=max(ans,abs(a[i]-m));
37     }
38     printf("%.2lf",ans);
39 }
View Code

开始得了8分,错误代码:

for(int i=1;i<=n;i++)
    {
    	if(a[i]==minn) continue;
    	if(a[i]==maxx) continue;
忽略了极值有>=2个的情况。例3,3,4,4,只continue一个3.一个4
T09 直方图
描述

给定一个非负整数数组,统计里面每一个数的出现次数。我们只统计到数组里最大的数。

假设 Fmax (Fmax < 10000)是数组里最大的数,那么我们只统计 {0,1,2.....Fmax} 里每个数出现的次数。

输入
第一行n是数组的大小。1 <= n <= 10000。
紧接着一行是数组的n个元素。

输出
按顺序输出每个数的出现次数,一行一个数。如果没有出现过,则输出0。
对于例子中的数组,最大的数是3,因此我们只统计{0,1,2,3}的出现频数。
技术分享
样例输入
5
1 1 2 3 1
样例输出
0
3
1 
1
样例

技术分享
 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int n,sum[10001],x,maxx;
 5 int main()
 6 {
 7        cin>>n;
 8        for(int i=1;i<=n;i++)
 9         {
10             scanf("%d",&x);
11             sum[x]++;
12             if(x>maxx) maxx=x;
13         }
14        for(int i=0;i<=maxx;i++)
15        printf("%d\n",sum[i]);
16 }
View Code
T10 找最大数序列
描述

输入n行,每行不超过100个无符号整数,无符号数不超过4位。请输出最大整数以及最大整数所在的行号(行号从1开始)。如果该数据在多个行中出现,则按从小到大输出相应行号,行号之间以一个逗号分开。

输入
一行输入一个正整数n(n <= 30)。
之后的n行,每行包含不超过100个无符号整数,整数之间以一个逗号分开。
输出
第一行:最大整数;
第二行:最大整数所在的行编号,逗号间隔。
技术分享
样例输入
6
1,3,5,23,6,8,14
20,22,13,4,16
23,12,17,22
2,6,10,9,3,6
22,21,20,8,10
22,1,23,6,8,19,23
样例输出
23
1,3,6
样例

本题的读入方式有好几种。

1、按字符串把一行读进去,再根据逗号断开。

2、一个字符一个字符的读。

以下是第二种方法,读入方法思路来源于读入优化。

技术分享
 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 int n,h,x,sl=1,l=1;
 6 int ans[3001],sum,maxn=-1;
 7 char c;
 8 int a[31][102];
 9 void init()//修改的读入优化 
10 {
11     c=getchar();
12     while(h<=n)
13     {
14         if(c==\n) 
15           {
16             if(h) 
17             {
18                 a[h][l]=x;
19                 a[h][l+1]=99999;
20                 x=0;
21             }
22             h++;
23             l=1;
24             if(h<=n)
25             c=getchar();
26             continue;
27         }
28         if(c==,) 
29         {
30             a[h][l]=x;
31             l++;
32             x=0;
33             c=getchar();
34             continue;
35         }
36         while(c>=0&&c<=9)
37         {
38         x=x*10+c-0;
39         c=getchar();
40         }
41     }
42 }
43 int main()
44 {
45     cin>>n;
46     init();
47     for(int i=1;i<=n;i++)
48     {
49         int j=1;
50         while(a[i][j]!=99999)
51         {
52             if(a[i][j]==maxn&&ans[sum]!=i)//一行里可能有好几个最大数,但只能输出一个,所以ans【sum】!=i 
53               ans[++sum]=i;
54             else if(a[i][j]>maxn)
55             {
56                 sum=0;
57                 ans[++sum]=i;
58                 maxn=a[i][j];
59             }
60             j++;
61         }
62     }
63     cout<<maxn<<endl;
64     for(int i=1;i<sum;i++) cout<<ans[i]<<,;
65     cout<<ans[sum];
66 }
View Code

第二种方法的另一种代码参照链接,来源:myj

T11 连续出现的字符

描述

给定一个字符串,在字符串中找到第一个连续出现至少k次的字符。

输入

第一行包含一个正整数k,表示至少需要连续出现的次数。1 <= k <= 1000。
第二行包含需要查找的字符串。字符串长度在1到1000之间,且不包含任何空白符。

输出

若存在连续出现至少k次的字符,输出该字符;否则输出No。

技术分享
样例输入
3
abcccaaab
样例输出
c
样例
技术分享
 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 char a[1001];
 5 int n,now=1; 
 6 using namespace std;
 7 int main()
 8 {
 9     cin>>n;
10     cin>>a;
11     if(n==1)
12     {
13         cout<<a[0];
14         return 0;
15     }
16     for(int i=1;i<strlen(a);i++)
17     {
18         if(a[i]==a[i-1]) now++;
19         else now=1;
20         if(now==n)
21         {
22             cout<<a[i];
23             return 0;
24         }
25     }
26     cout<<"No";
27 } 
View Code

T12 最长平台

描述

已知一个已经从小到大排序的数组,这个数组的一个平台(Plateau)就是连续的一串值相同的元素,并且这一串元素不能再延伸。例如,在 1,2,2,3,3,3,4,5,5,6中1,2-2,3-3-3,4,5-5,6都是平台。试编写一个程序,接收一个数组,把这个数组最长的平台找出 来。在上面的例子中3-3-3就是最长的平台。

输入

第一行有一个整数n(n <= 1000),为数组元素的个数。第二行有n个整数,整数之间以一个空格分开。

输出

输出最长平台的长度。

技术分享
样例输入
10
1 2 2 3 3 3 4 5 5 6
样例输出
3
样例
技术分享
#include<cstdio>
#include<iostream>
#include<cstring>
int n,now=1,maxn=1,x,last; 
using namespace std;
int main()
{
    cin>>n;
    cin>>last;
    for(int i=2;i<=n;i++)
    {
        scanf("%d",&x);
        if(x==last) now++;
        else now=1;
        if(now>maxn) maxn=now;
        last=x;
    }
    cout<<maxn;
} 
View Code

T13 整数去重

描述

给定含有n个整数的序列,要求对这个序列进行去重操作。所谓去重,是指对这个序列中每个重复出现的数,只保留该数第一次出现的位置,删除其余位置。

输入

输入包含两行:
第一行包含一个正整数n(1 <= n <= 20000),表示第二行序列中数字的个数;
第二行包含n个整数,整数之间以一个空格分开。每个整数大于等于10、小于等于100。

输出

输出只有一行,按照输入的顺序输出其中不重复的数字,整数之间用一个空格分开。

技术分享
样例输入
5
10 12 93 12 75
样例输出
10 12 93 75
样例
技术分享
 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 int n,now=1,maxn=1;
 5 int a[20001];
 6 bool v[101];
 7 using namespace std;
 8 int main()
 9 {
10     cin>>n;
11     for(int i=1;i<=n;i++)
12     {
13         scanf("%d",&a[i]);
14         if(!v[a[i]]) 
15         {
16            v[a[i]]=true;
17            cout<<a[i]<<  ;
18         } 
19     }    
20 } 
View Code

T 14铺地毯

描述

为了准备一个独特的颁奖典礼,组织者在会场的一片矩形区域(可看做是平面直角坐标系的第一象限)铺上一些矩形地毯。一共有n张地毯,编号从1到n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设,后铺的地毯覆盖在前面已经铺好的地毯之上。地毯铺设完成后,组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意:在矩形地毯边界和四个顶点上的点也算被地毯覆盖。

输入输出样例1说明:如下图,1号地毯用实线表示,2号地毯用虚线表示,3号用双实线表示,覆盖点(2,2)的最上面一张地毯是3号地毯。

输入输出样例2说明:如下图,1号地毯用实线表示,2号地毯用虚线表示,3号用双实线表示,覆盖点(4,5)的最上面一张地毯是3号地毯。

技术分享

 

输入

输入共n+2行。
第一行,一个整数n,表示总共有n张地毯。
接下来的n行中,第i+1行表示编号i的地毯的信息,包含四个正整数a,b,g,k,每两个整数之间用一个空格隔开,分别表示铺设地毯的左下角的坐标(a,b)以及地毯在x轴和y轴方向的长度。
第n+2行包含两个正整数x和y,表示所求的地面的点的坐标(x,y)。

对于30%的数据,有n≤2;
对于50%的数据,0≤a, b, g, k≤100;
对于100%的数据,有0≤n≤10,000,0≤a, b, g, k≤100,000。

输出

输出共1行,一个整数,表示所求的地毯的编号;若此处没有被地毯覆盖则输出-1。

技术分享
样例输入
样例 #13
1 0 2 3
0 2 3 3
2 1 3 3
2 2

样例 #23
1 0 2 3
0 2 3 3
2 1 3 3
4 5
样例输出
样例 #13

样例 #2-1
样例

倒着往前找

技术分享
 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int n,x,y;
 5 int a[10001],b[10001],g[10001],k[10001];
 6 int main()
 7 {
 8     scanf("%d",&n);
 9     for(int i=1;i<=n;i++)
10      scanf("%d%d%d%d",&a[i],&b[i],&g[i],&k[i]);
11     scanf("%d%d",&x,&y);
12     for(int i=n;i>=1;i--)
13     {
14         if(x>=a[i]&&x<=a[i]+g[i]&&y>=b[i]&&y<=b[i]+k[i])
15          {
16              cout<<i;
17              return 0;
18          }
19     }
20     cout<<-1;
21 }
View Code

T15 接水问题 

描述

学校里有一个水房,水房里一共装有 m 个龙头可供同学们打开水,每个龙头每秒钟的供水量相等,均为 1。

现在有 n 名同学准备接水,他们的初始接水顺序已经确定。将这些同学按接水顺序从 1 到 n 编号,i号同学的接水量为 wi。接水开始时,1 到 m 号同学各占一个水龙头,并同时打开水龙头接水。当其中某名同学 j 完成其接水量要求 wj后,下一名排队等候接水的同学 k 马上接替 j 同学的位置开始接水。这个换人的过程是瞬间完成的,且没有任何水的浪费。即 j 同学第 x 秒结束时完成接水,则 k 同学第 x+1 秒立刻开始接水。 若当前接水人数 n’不足 m,则只有 n’个龙头供水,其它 m-n’个龙头关闭。

现在给出 n 名同学的接水量,按照上述接水规则,问所有同学都接完水需要多少秒。

输入

第 1 行2 个整数 n 和 m,用一个空格隔开,分别表示接水人数和龙头个数。
第 2 行 n 个整数 w1、w2、……、wn,每两个整数之间用一个空格隔开,wi表示 i 号同学的接水量。

1 ≤ n ≤ 10000,1 ≤ m ≤ 100 且 m ≤ n;
1 ≤ wi ≤ 100。

输出

输出只有一行,1 个整数,表示接水所需的总时间。

技术分享
样例输入
样例 #15 3
4 4 1 2 1

样例 #28 4
23 71 87 32 70 93 80 76
样例输出
样例 #14

样例 #2163
样例

利用优先队列,将其转化为小根堆,前m个先存进去,每次取出队首元素加上下一个再存进去,最后一只清空队列,最后一个数即为答案

技术分享
 1 #include<iostream>
 2 #include<queue>
 3 #include<cstdio>
 4 using namespace std;
 5 priority_queue<int,vector<int>,greater<int> >p;//转化为小根堆
 6 int n,m,x,ans;
 7 int main()
 8 {
 9     scanf("%d%d",&n,&m);
10     for(int i=1;i<=m;i++)
11     {
12         scanf("%d",&x);
13         p.push(x);
14     }
15     for(int i=m+1;i<=n;i++)
16     {
17         scanf("%d",&x);
18         int t=p.top();
19         p.pop();
20         t+=x;
21         p.push(t);
22     }
23     while(!p.empty())
24     {
25         ans=p.top();
26         p.pop();
27     }
28     printf("%d",ans);
29 }
View Code

 

noi题库(noi.openjudge.cn) 1.9编程基础之顺序查找T06——T15