首先，这次练习感觉很无奈啊，不能用stl，让本来简单的问题变得有些复杂了。
排序的话，快排的效率应该是最高的吧，现成的函数不能用，那么只能手写了，先贴一下手写的快排吧
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[50];
void qs(int begin,int end)
{
if(begin>end)return;
int l=begin,r=end;
int key=a[begin];
while(l<r)
{
while(a[r]>=key&&l<r)r--;
swap(a[l],a[r]);
while(a[l]<=key&&l<r)l++;
swap(a[l],a[r]);
}
qs(begin,l-1);
qs(r+1,end);
}
int main()
{
int n;
while(cin>>n)
{
for(int i=0;i<n;i++)cin>>a[i];
qs(0,n-1);
for(int i=0;i<n;i++)cout<<a[i]<<" ";
cout<<endl;
}
return 0;
}
首先第一题，有奇数个数，找出出现次数超过（n+1）/2的那个，思路很简单，排序，输出中间那个数，我首先是用选择排序试了下，果断t了，接着就考虑发挥上面代码的功效，结果也奇葩的T了，这让我很是头疼，赛后用sort交了下，ac了。也想过标记数的出现次数，但是map不能用，又觉得开数组标记不现实，所以没尝试，但赛后发现这种方法是可行的，数据较水。在oj上原题的discuss里，看到了一种好方法，没有涉及排序，个人感觉很牛掰，感觉自己的思路过于局限了，这是那方法的代码：
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int n,m,num,s;
while(scanf("%d",&n)!=EOF)
{
num=0;
for(int i=0;i<n;i++)
{
scanf("%d",&m);
if(num==0)
{
s=m;
num++;
}
else
{
if(m!=s)num--;
else num++;
}
}
printf("%d\n",s);
}
return 0;
}
第二题，显然较水，随便排下就过了。
第三题也不难，这里感觉考的不是排序，而是熟练的拆分字符串将其转化为数字，只要思路清晰，基本不难。
第四题，是关于时钟指针夹角的排序，总共就5个值排序，所以这里的排序并不是重点，重点是理解角度怎么算，题目中输入的时间采取的是24小时制的，而大家知道时钟一圈是12小时，这里就涉及到相关转换。总之理解了题意，ac并不难，就是题目读的很麻烦，在比赛时间内未能ac。。。。。。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int t;
double am,ah;
struct node
{
double h,m,hh,angle;
} p[5],temp;
char ss;
int main()
{
scanf("%d",&t);
while(t--)
{
for(int i=0; i<5; i++)
{
cin>>p[i].h>>ss>>p[i].m;
if(p[i].h>12)p[i].hh=p[i].h-12;
else p[i].hh=p[i].h;
am=p[i].m*6;
ah=p[i].hh*30+p[i].m/2.0;
p[i].angle=ah>am?ah-am:am-ah;
if(p[i].angle>180)p[i].angle=360.0-p[i].angle;
//cout<<ah<<" "<<am<<" "<<p[i].angle<<endl;
}
for(int i=0; i<3; i++)
{
for(int j=i+1; j<5; j++)
{
if(p[i].angle>p[j].angle)
{
temp=p[i];
p[i]=p[j];
p[j]=temp;
}
else if(p[i].angle==p[j].angle)
{
if(p[i].h>p[j].h)
{
temp=p[i];
p[i]=p[j];
p[j]=temp;
}
else if(p[i].h==p[j].h)
{
if(p[i].m>p[j].m)
{
temp=p[i];
p[i]=p[j];
p[j]=temp;
}
}
}
}
}
if(p[2].h<10)cout<<"0"<<p[2].h;
else cout<<p[2].h;
cout<<":";
if(p[2].m<10)cout<<"0"<<p[2].m<<endl;
else cout<<p[2].m<<endl;
}
return 0;
}
第五题，考的是结构体排序，这道题让我很是窝火啊，明明不难，但我各种wa，还找不出原因，让我蛋蛋碎了一地的感觉啊，最后还是用sort过的。。。。。。。。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,g,fen[15],num,k,ans;
struct node
{
string name;
int sum;
}p[1005],temp;
bool cmp(node x,node y)
{
if(x.sum==y.sum)return x.name<y.name;
else return x.sum>y.sum;
}
int main()
{
while(scanf("%d",&n)&&n)
{
ans=0;
scanf("%d%d",&m,&g);
for(int i=1;i<=m;i++)scanf("%d",&fen[i]);
for(int i=0;i<n;i++)
{
cin>>p[i].name;
scanf("%d",&num);
p[i].sum=0;
for(int j=0;j<num;j++)
{
scanf("%d",&k);
p[i].sum+=fen[k];
}
if(p[i].sum>=g)ans++;
}
/*for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
if(p[i].sum<p[j].sum)
{
temp=p[i];
p[i]=p[j];
p[j]=temp;
}
else if(p[i].sum==p[j].sum)
{
if(p[i].name>p[j].name){
temp=p[i];
p[i]=p[j];
p[j]=temp;}
}
}
if(p[i].sum>=g)ans++;
else break;
}*/
sort(p,p+n,cmp);
printf("%d\n",ans);
for(int i=0;i<ans;i++)
{
cout<<p[i].name;
printf(" %d\n",p[i].sum);
}
}
return 0;
}
第六题，先是对于n个数俩俩组合成N*(N-1)/2个数再排序，输出前m大的数。组合后数蛮多的，排序起来也不好办（特别是在不能stl的情况下）。。。最后是记录数的个数，过的。。。。对于群邮里的正解我没怎么看懂。。。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int f[1000001],a[3001];
int n,m,ma,num;
void solve()
{
printf("%d",ma);
f[ma]--;
m--;
for(int i=ma;i>=0;i--)
{
if(f[i])
{
while(f[i]--)
{
printf(" %d",i);
m--;
if(!m)return;
}
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(f,0,sizeof(f));
ma=0;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(int i=n-1;i>0;i--)
{
for(int j=i-1;j>=0;j--)
{
num=a[i]+a[j];
f[num]++;
if(num>ma)ma=num;
}
}
solve();
printf("\n");
}
return 0;
}
第七题纯粹找规律，哪要排序啊。。。。
第八题也较水，手写快排飘过。