小测试4.10
今天晚上进行可小测试
来看看题目都咋样吧!
附近的最小值
Description
fly学姐有一个序列a[1],a[2],...,a[n]。
给定一个正整数k，请问对于每一个1到n之间的序号i，a[i−k],a[i−k+1],...,a[i+k]这2k+1个数中的最小值是多少？
当某个下标超过1到n的范围时，数不存在，求最小值时只取存在的那些值。
Input
输入的第一行包含一整数n。
第二行包含n个整数，分别表示a[1],a[2],...,a[n]。
第三行包含一个整数k。
Output
输出一行，包含n个整数，分别表示对于每个序号求得的最小值
Sample Input 1
5 5 2 7 4 3 1
Sample Output 1
2 2 2 3 3
Hint
对于 30% 的评测用例，1<=n<=1000，1<=a[i]<=1000。
对于 50% 的评测用例，1<=n<=10000，1<=a[i]<=10000。
对于所有评测用例，1<=n<=1000000，1<=a[i]<=100000
对题目的第一反应就是枚举
完全的按照题目给的思路来,
没想到不会卡时间一遍过
#include<stdio.h>int a[1000001];
int ans[1000001]={0};//答案数组int main(){
int n,k;
scanf("%d",&n);
for(int j=1;j<=n;j++)
scanf("%d",&a[j]);
scanf("%d",&k);for(int j=1;j<=n;j++){int minr=10000999;for(int g=j-k;g<=j+k;g++){if(g>=1&&g<=n&&a[g]<minr){minr=a[g];ans[j]=a[g];}//每个循环得出一个答案}
}for(int h=1;h<=n;h++)printf("%d ",ans[h]);//直接输出答案,不会存在没答案的return 0;
}第一个题目,还是非常的友好的呀 ,爱了,爱了
第二个
环形杀人事件
Description
一天，杀人狂魔李华突然想要杀人，就把他抓来的N个英雄依次分配一个编号，第一个人的编号为1号，第二个人的编号为2号，第N个人的编号就为N号，他们按顺序围成一个环形，现在给出一个数字M，第一个人开始从1报数，第二个人报的数就是2，依次类推，报到M这个数字的人被杀了（1a秒了），紧接着从被杀了的这个人的下一个人重新开始从1报数，和上面过程类似，报到M的人被杀，直到N个人全部被杀掉，请问，这个被杀的顺序是什么？
Input
给出两个正整数N、M
Output
输出被杀的顺序
Sample Input 1
10 3
Sample Output 1
3 6 9 2 7 1 8 5 10 4
Hint
1<n<=10000
1<m<=100
这个我一看,没错就是递归来搞定,难度不大就是,写代码得细心,不要因为一点点的逻辑卡测试半天
而且可以用链表来写,用c++的我倒是觉得可以但是c语言手写链表,万一错了一点,从那开始纠正呀
可以用普普通通的数组加上一个标记数组解决的事情就不要太麻烦
上代码
#include<stdio.h>
int a[100050]={0};
int n,m;void kill(int x,int y){a[y]=1;printf("%d ",y);x--;
if(x==0){return;
}
else{int h=0;while(h!=m){y++;if(y>n){y=y-n;//我的数组是1到n所以不可以用取余,会出现0的(搞了半天)}if(a[y]==0){h++;}}kill(x,y);
}}int main(){
scanf("%d%d",&n,&m);
kill(n,m);
return 0;
}难度也是一般般啦(不可以乱说的)
下一个
Description
lx学长是一个养羊大户，有成千上百个羊圈。可是却一次也没来羊圈帮过忙，今天lx学长被叫来羊圈给羊羊们施展成双成对大法。关于成双成对大法，lx学长虽然没有实践过，但是他表现得胸有成竹。而成双成对大法需要类型相同的羊才能完成，不过lx学长不知道每个羊圈能否完成成双成对大法，lx学长太懒了，想请你帮帮他。
羊圈里面有三种类型的羊，分别为(),[].{}，lx学长的羊圈和别家的羊圈不同，羊圈中也可能不只有羊。
lx学长会给你一串字符，不超过100个字符，可能包括括号、数组、字母、标点符号、空格，你的任务是检查这一串字符中的(),[],{}是否匹配。
Input
一行数据，不超过100个字符并含有( ,) ,[, ],{, }一个或多个。
Output
如果匹配就输出“yes”，不匹配输出“no”
Sample Input 1
sin(20+10)
Sample Output 1
yes
Sample Input 2
{[}]
Sample Output 2
no
这个稍微的难了一点,但是你要是掌握了栈并且你想起了栈
那这题目对你而言,不过是细节的处理的问题了
遇到左符号就入栈,遇到右边的就出栈比较,符合则继续,不符合就退出循环
要是比要最后栈空了,就是符合的
上代码看看
#include<stdio.h>
#include<string.h>char a[12000];
char b[12000];int main()
{gets(a);int n=strlen(a);int top=0;int ans=1;for(int g=0; g<n; g++){switch(a[g]){case '(':b[top]='(';top++;break;case '[':b[top]='[';top++;break;case '{':b[top]='{';top++;break;case ')':if(top>=1){top--;if(b[top]!='(')ans=0;}else{ans=0;}break;case ']':if(top>=1){top--;if(b[top]!='[')ans=0;}else{ans=0;}break;case '}':if(top>=1){top--;if(b[top]!='{')ans=0;}else{ans=0;}break;default:break;}if(ans==0)break;}if(ans==1&&top==0){printf("yes\\n");}else{printf("no\\n");}return 0;
}记得出栈比较是拿另外的一半符号比较,不和自己比,错了看了半天觉得没问题,反复测试数据发现了
我真的是离谱 ,遇到}就出栈看是不是}(咋可能是呀,右符号不入栈的)
下一个,下一个
下一个更大元素
Description
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
Input
第一行为n，代表nums的大小（1≤n≤10000）
第二行 n个数
Output
输出一个长度n的数组，每个元素代表对应的循环数组中比i大的下一个元素
Sample Input 1
3 1 2 1
Sample Output 1
2 -1 2
Sample Input 2
5 1 2 3 4 3
Sample Output 2
2 3 4 -1 4
这题目也是枚举呀
从1枚举到n
然后输出完全可以的,废话不多讲了直接上代码
#include<stdio.h>int n,nums[100000];void prin(int y){
if(y==n+1){return ;
}
else{for(int j=y+1;;j++){if(j>n)j=j-n;if(nums[j]>nums[y]){printf("%d ",nums[j]);break;}if(j==y){printf("-1 ");break;}}prin(y+1);}
}int main(){scanf("%d",&n);
for(int j=1;j<=n;j++)scanf("%d",&nums[j]);prin(1);return 0;
}呜呜呜我是菜鸡,就写了折磨多
第5个不对堆,所以时间老是超限明天我要ko那题,再去看看最后一个
ok
今天撒花谢幕啦啦啦啦!
