题目1 : Exam13_Median
时间限制:5000ms
单点时限:1000ms
内存限制:256MB
描述
给定一个正整数数组，请求出自第一个元素开始到每个元素为终点的中位数。
输入
第一行：N(1<N<=1000)，代表数组的长度
第二行：N个整数，作为数组的元素，空格分开
输出
N个整数，空格隔开；第一位是数组第一个元素，第二位是前两个元素的上中位数……
样例输入
5
4 6 9 4 5
样例输出
4 4 6 4 5
AC代码
#include<stdio.h>
/// 化问题为求单个数组的中位数
void px(int*a,int i) // 地址传递，可节约运行时间
{
int j,jj;
for(j=i;j>0;j--)
for(jj=0;jj<j;jj++)
{
if(a[jj]>a[jj+1]) // 交换两个数
{
a[jj]+=a[jj+1];
a[jj+1]=a[jj]-a[jj+1];
a[jj]=a[jj]-a[jj+1];
}
}
printf("%d ",a[i/2]);
}
main()
{
int n,i;
scanf("%d",&n);
int a[n];
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)
{
px(a,i);
}
return 0;
}
时间限制:5000ms
单点时限:1000ms
内存限制:256MB
描述
数组小和的定义如下：
例如：数组s = [1, 3, 5, 2, 4, 6]，在s[1]的左边小于或等于s[1]的数的和为1，在s[2]的左边小于或等于s[2]的数有1和3，求和为4，……，将所有位置的左边比它小或者等于的数的和相加起来就是真个数组的小和。
给定一个数组，输出数组的小和。
输入
第一行：N(1<N<=100000)，代表数组的长度
第二行：N个整数(<=100)，作为数组的元素，空格分开
输出
数组的小和
样例输入
5
58 74 14 39 15
样例输出
86
AC代码 ---Java
//计算数组的小和
import java.util.*;
public class Main{
//方法二(归并排序)，时间复杂度为O(NlogN),额外的空间复杂度为O(N)
public static int GetMinArrSum2(int[]arr)
{
if(arr==null||arr.length==0)
{
return 0;
}
return func(arr,0,arr.length-1);
}
//运用递归函数实现
public static int func(int[]arr,int l,int r)
{
//递归的出口
if(l==r)
{
return 0;
}
int mid=(l+r)/2; //中间位置的数
return func(arr,l,mid)+func(arr,mid+1,r)+merge(arr,l,mid,r);
}
//归并排序的具体实现
public static int merge(int[]arr,int l,int mid,int r)
{
int[]h=new int[r-l+1]; //开辟O(N)的空间
int hi=0;
int i=l;
int j=mid+1;
int smallSum=0;
while(i<=mid&&j<=r)
{
if(arr[i]<=arr[j])
{
smallSum+=arr[i]*(r-j+1);
h[hi++]=arr[i++];
}else
{
h[hi++]=arr[j++];
}
}
for(;(j<r+1)||(i<mid+1);j++,i++)
{
h[hi++]=i>mid?arr[j]:arr[i];
}
//对原数组的重新赋值
for(int k=0;k!=h.length;k++)
{
arr[l++]=h[k];
}
return smallSum;
}
//打印数组的内容
public static void PrintArr(int[]arr)
{
for(int i=0;i<arr.length;i++)
{
System.out.print(arr[i]+" ");
}
System.out.println();
}
public static void main(String[]args)
{
//System.out.println("Hello");
Scanner in = new Scanner(System.in);
int a = in.nextInt();
int[] arr = new int[a];
for(int i = 0;i<a;i++){
arr[i]=in.nextInt();
}
System.out.println(GetMinArrSum2(arr));
}
}
题目3 : Exam15_MaxHeap
时间限制:5000ms
单点时限:1000ms
内存限制:256MB
描述
给定一个数组，求最小的K个数。由于数组规模很大，请精心设计算法。
输入
第一行：N(1<N<=100000)，代表数组的长度
第二行：K(<=1000,<N)，代表求从小到大的K个数
第三行：N个整数，作为数组的元素，空格分开
输出
从小到大输出K个数组中最小的数，空格隔开
样例输入
10
3
1 3 4 2 6 7 8 10 11 12
样例输出
1 2 3
AC代码
#include<stdio.h>
// k 个循环，求出最小的k个数即可结束
void px(int*a,int n,int k)
{
int jj,j;
for(jj=0;jj<k;jj++)
{
for(j=n-2;j>=jj;j--)
{
if(a[j]>a[j+1])
{
a[j]+=a[j+1];
a[j+1]=a[j]-a[j+1];
a[j]=a[j]-a[j+1];
}
}
printf("%d ",a[jj]);
}
}
main()
{
int n,a[100000],i,s=0,k;
scanf("%d",&n);
scanf("%d",&k);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
px(a,n,k);
return 0;
}
题目4 : Exam16_CombineString
时间限制:5000ms
单点时限:1000ms
内存限制:256MB
描述
给定一个字符串类型的数组strs，请找到一种拼接顺序，使得将所有的字符串拼接起来组成的大字符串是所有可能性中字典顺序最大的，并输出这个大字符串。
输入
第一行：N(1<N<=100)，代表数组的长度
第二行：N个字符串，作为数组的元素，空格分开，字符串长度<=10
输出
字典序最大的大字符串
样例输入
5
a ac ab def d
样例输出
defdacaba
AC代码
#include<stdio.h>
#include<string.h>
main()
{
char str[101][11];
char tp1[21],tp2[21],tmp[11];
int n,i,f,j;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%s",&str[i]);
for(j=n-1;j>0;j--)
for(i=0;i<j;i++)
{
strcpy(tp1,str[i]);
strcat(tp1,str[i+1]); // tp1= str[i]+str[i+1]
strcpy(tp2,str[i+1]);
strcat(tp2,str[i]); // tp2= str[i+1]+str[i]
f=strcmp(tp1,tp2); // 比较结果给f
if(f<0)
{ // 交换
strcpy(tmp,str[i]);
strcpy(str[i],str[i+1]);
strcpy(str[i+1],tmp);
}
}
for(i=0;i<n;i++)
printf("%s",str[i]);
return 0;
}
题目5 : Exam17_NewOrder
时间限制:5000ms
单点时限:1000ms
内存限制:256MB
描述
一般我们在对字符串排序时，都会按照字典序排序。当字符串只包含小写字母时，相当于按字母表"abcdefghijklmnopqrstuvwxyz"的顺序排序。
现在我们打乱字母表的顺序，得到一个26个字母的新顺序:bdceafghijklmnopqrstuvwxyz，代表'b'排在'd'前，'d'在'c'前，'c'在'e'前……
给定N个字符串，请你按照新的字母顺序对它们排序。
输入
第一行包含一个整数N。(1 <= N <= 1000)
第二行包含26个字母，代表新的顺序。
以下N行每行一个字符串S。 (|S| <= 100)
输出
按新的顺序输出N个字符串，每个字符串一行。
样例输入
5
bdceafghijklmnopqrstuvwxyz
abcde
adc
cda
cad
ddc
样例输出
ddc
cda
cad
abcde
adc
半AC只跑了80分 还得改进。
#include<stdio.h>
#include<string.h>
char qj[1001][101];/// 将输入数组化为abc..并保存
int sum=0;
void change(char *aa,char *bb,int len,char *tp)// 对应abc。。保存
{
int i,j,jj;
for(j=0;j<len;j++)
for(i=0;i<26;i++)
{
if(tp[j]==aa[i])
{
tp[j]=bb[i];
break;
}
}
strcpy(qj[sum++],tp);
}
main()
{
char tp[101];
char str[1001][101]; // 保存输入的数组
char aa[26],bb[26];
int n,i,len,f;
scanf("%d",&n);
scanf("%s",&aa); // a 新顺序
for(i=0;i<n;i++)
scanf("%s",&str[i]); // 多行字符串
for(i=0;i<26;i++)
bb[i]='a'+i; // b 原顺序
for(i=0;i<n;i++)
{
strcpy(tp,str[i]);
change(aa,bb,strlen(str[i]),tp);
}
for(sum=n-1;sum>0;sum--)
for(i=0;i<sum;i++)
{
// 比较 排序
f=strcmp(qj[i],qj[i+1]);
if(f>0)
{
strcpy(tp,qj[i]);
strcpy(qj[i],qj[i+1]);
strcpy(qj[i+1],tp);
// 同时对str[]排序
strcpy(tp,str[i]);
strcpy(str[i],str[i+1]);
strcpy(str[i+1],tp);
}
}
for(i=0;i<n;i++)
printf("%s\n",str[i]); // 输出
return 0;
}
