題目1 : Exam13_Median
時間限制:5000ms
單點(diǎn)時限:1000ms
內(nèi)存限制:256MB
描述
給定一個正整數(shù)數(shù)組，請求出自第一個元素開始到每個元素為終點(diǎn)的中位數(shù)。
輸入
第一行：N(1<N<=1000)，代表數(shù)組的長度
第二行：N個整數(shù)，作為數(shù)組的元素躯舔，空格分開
輸出
N個整數(shù)，空格隔開；第一位是數(shù)組第一個元素髓迎，第二位是前兩個元素的上中位數(shù)……
樣例輸入
5
4 6 9 4 5
樣例輸出
4 4 6 4 5
AC代碼
#include<stdio.h>
/// 化問題為求單個數(shù)組的中位數(shù)
void px(int*a,int i) // 地址傳遞，可節(jié)約運(yùn)行時間
{
int j,jj;
for(j=i;j>0;j--)
for(jj=0;jj<j;jj++)
{
if(a[jj]>a[jj+1]) // 交換兩個數(shù)
{
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
單點(diǎn)時限:1000ms
內(nèi)存限制:256MB
描述
數(shù)組小和的定義如下：
例如：數(shù)組s = [1, 3, 5, 2, 4, 6]挡爵，在s[1]的左邊小于或等于s[1]的數(shù)的和為1竖般，在s[2]的左邊小于或等于s[2]的數(shù)有1和3，求和為4茶鹃，……涣雕，將所有位置的左邊比它小或者等于的數(shù)的和相加起來就是真?zhèn)€數(shù)組的小和。
給定一個數(shù)組闭翩，輸出數(shù)組的小和挣郭。
輸入
第一行：N(1<N<=100000)，代表數(shù)組的長度
第二行：N個整數(shù)(<=100)疗韵，作為數(shù)組的元素兑障，空格分開
輸出
數(shù)組的小和
樣例輸入
5
58 74 14 39 15
樣例輸出
86
AC代碼 ---Java
//計(jì)算數(shù)組的小和
import java.util.*;
public class Main{
//方法二(歸并排序)，時間復(fù)雜度為O(NlogN),額外的空間復(fù)雜度為O(N)
public static int GetMinArrSum2(int[]arr)
{
if(arr==null||arr.length==0)
{
return 0;
}
return func(arr,0,arr.length-1);
}
//運(yùn)用遞歸函數(shù)實(shí)現(xiàn)
public static int func(int[]arr,int l,int r)
{
//遞歸的出口
if(l==r)
{
return 0;
}
int mid=(l+r)/2; //中間位置的數(shù)
return func(arr,l,mid)+func(arr,mid+1,r)+merge(arr,l,mid,r);
}
//歸并排序的具體實(shí)現(xiàn)
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];
}
//對原數(shù)組的重新賦值
for(int k=0;k!=h.length;k++)
{
arr[l++]=h[k];
}
return smallSum;
}
//打印數(shù)組的內(nèi)容
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
單點(diǎn)時限:1000ms
內(nèi)存限制:256MB
描述
給定一個數(shù)組蕉汪，求最小的K個數(shù)流译。由于數(shù)組規(guī)模很大，請精心設(shè)計(jì)算法者疤。
輸入
第一行：N(1<N<=100000)福澡，代表數(shù)組的長度
第二行：K(<=1000,<N)，代表求從小到大的K個數(shù)
第三行：N個整數(shù)驹马，作為數(shù)組的元素革砸，空格分開
輸出
從小到大輸出K個數(shù)組中最小的數(shù)，空格隔開
樣例輸入
10
3
1 3 4 2 6 7 8 10 11 12
樣例輸出
1 2 3
AC代碼
#include<stdio.h>
// k 個循環(huán)糯累，求出最小的k個數(shù)即可結(jié)束
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
單點(diǎn)時限:1000ms
內(nèi)存限制:256MB
描述
給定一個字符串類型的數(shù)組strs算利，請找到一種拼接順序，使得將所有的字符串拼接起來組成的大字符串是所有可能性中字典順序最大的泳姐，并輸出這個大字符串效拭。
輸入
第一行：N(1<N<=100)，代表數(shù)組的長度
第二行：N個字符串，作為數(shù)組的元素允耿，空格分開借笙，字符串長度<=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); // 比較結(jié)果給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
單點(diǎn)時限:1000ms
內(nèi)存限制:256MB
描述
一般我們在對字符串排序時，都會按照字典序排序较锡。當(dāng)字符串只包含小寫字母時业稼，相當(dāng)于按字母表"abcdefghijklmnopqrstuvwxyz"的順序排序。
現(xiàn)在我們打亂字母表的順序蚂蕴，得到一個26個字母的新順序:bdceafghijklmnopqrstuvwxyz低散，代表'b'排在'd'前，'d'在'c'前骡楼，'c'在'e'前……
給定N個字符串熔号，請你按照新的字母順序?qū)λ鼈兣判颉?br> 輸入
第一行包含一個整數(shù)N。(1 <= N <= 1000)
第二行包含26個字母鸟整，代表新的順序引镊。
以下N行每行一個字符串S。 (|S| <= 100)
輸出
按新的順序輸出N個字符串篮条，每個字符串一行弟头。
樣例輸入
5
bdceafghijklmnopqrstuvwxyz
abcde
adc
cda
cad
ddc
樣例輸出
ddc
cda
cad
abcde
adc
半AC只跑了80分 還得改進(jìn)。
#include<stdio.h>
#include<string.h>
char qj[1001][101];/// 將輸入數(shù)組化為abc..并保存
int sum=0;
void change(char *aa,char *bb,int len,char *tp)// 對應(yīng)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]; // 保存輸入的數(shù)組
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;
}
