这次的周赛不能用stl，开始不知道，全是用stl写滴，最后写了下快排，貌似快排写的不是很熟练，下面还是小结下。
快排代码：
void sort(int begin,int end)
{
if(begin>=end)
return ;
int i=begin,j=end,key=a[i];
while(i<j)
{
while(a[j]>=key&&i<j)
{
j--;
}
a[i]=a[j];
while(i<j&&a[i]<=key)
{
i++;
}
if(i<j)
{
a[j]=a[i];
}
}
a[i]=key;
sort(begin,i-1);
sort(i+1,end);
}
1001：这题值得深思。其实用数组标记次数就行，不过不能找最多的，只能找个数>n/2的，这样很花时间吧。用快排超时。
hdu1029
代码：
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<math.h>
#include<vector>
#define INF 10000000
#define MAXN 1000000
#define MAXL 1000
using namespace std;
bool cmp(int x,int y)
{
return x<y;
}
int a[MAXN];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=0; i<n; i++)
scanf("%d",&a[i]);
sort(a,a+n);
int count=1,ans=-1,m=a[0];
for(int i=1; i<n; i++)
{
if(a[i]==a[i-1])
{
count++;
}
else
{
count=1;
}
if(count>=(n+1)/2)
{
m=a[i];
}
}
printf("%d\n",m);
}
return 0;
}
1002：水题，直接快排。
hdu1040
1003
hdu 1106
水题，注意下字符串的处理，然后快排。
1004：注意时钟可能出现小数，还有时钟并不是整的角度，分钟转的时候会有小的角度。
hdu 1209
代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define maxn 100
using namespace std;
struct T
{
int h,m;
float n;
};
T tim[5];
bool cmp(T x, T y)
{
if(x.n!=y.n)
return x.n<y.n;
else
{
if(x.h!=y.h)
{
return x.h<y.h;
}
else
{
return x.m<y.m;
}
}
}
int main()
{
int t;
scanf("%d",&t);
float tmp;
while(t--)
{
for(int i=0;i<5;i++)
{
scanf("%d:%d",&tim[i].h,&tim[i].m);
tmp=fabs((tim[i].h%12)*30.0+30.0*tim[i].m/60-tim[i].m*6);
if(tmp<=180.0)
tim[i].n=tmp;
else
tim[i].n=360.0-tmp;
}
sort(tim,tim+5,cmp);
for(int i=0;i<5;i++)
printf("%02d:%02d %f\n",tim[i].h,tim[i].m,tim[i].n);
}
return 0;
}
1005：结构体排序，如果不用sort，就排两次就行。
hdu 1236
代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
struct ST
{
string name;
int goal;
}st[1005];
bool cmp(ST x,ST y)
{
if(x.goal!=y.goal)
{
return x.goal>y.goal;
}
else
{
return x.name<y.name;
}
}
int fenshu[15];
int main()
{
int n,m,g,num,nn;
while(scanf("%d",&n)!=EOF)
{
if(n==0) break;
scanf("%d%d",&m,&g);
nn=0;
for(int i=1;i<=m;i++)
scanf("%d",&fenshu[i]);
for(int i=1;i<=n;i++)
{
cin>>st[i].name>>num;
int agoal=0,k;
for(int j=1;j<=num;j++)
{
scanf("%d",&k);
agoal+=fenshu[k];
}
st[i].goal=agoal;
if(agoal>=g)
nn++;
}
sort(st+1,st+n+1,cmp);
printf("%d\n",nn);
for(int i=1;i<=nn;i++)
{
cout<<st[i].name<<' '<<st[i].goal<<endl;
}
}
return 0;
}
1006：用了个priotity_queue这个写的不是很熟练。
hdu 1280
用stl的代码：
#include<cstdio>
#include<iostream>
#include<queue>
#define maxn 3005
using namespace std;
priority_queue<int> q;
int n,m;
int a[maxn];
int main()
{
int tmp;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=0; i<n; i++)
{
scanf("%d",&a[i]);
}
for(int i=0; i<n; i++)
{
for(int j=i+1; j<n; j++)
{
tmp=a[i]+a[j];
q.push(tmp);
}
}
for(int i=0; i<m-1; i++)
{
tmp=q.top();
q.pop();
printf("%d ",tmp);
}
tmp=q.top();
q.pop();
printf("%d",tmp);
putchar('\n');
}
return 0;
}
不用stl的代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#define MAXN 1111
#define INF 1011111111
using namespace std;
int n, m;
int a[3333];
int partition(int a[], int low, int high)
{//快速排序中的一趟
int key;//作为枢轴来使用
key = a[low];
while(low < high)
{
while(low < high && a[high] >= key)
--high;
a[low] = a[high];
while(low < high && a[low] <= key)
++low;
a[high] = a[low];
}
a[low] = key;
return low;
}
void qsort(int a[], int low, int high)
{//快速排序的递归形式
int loc;
if(low < high)
{
loc = partition(a, low, high);//一趟排序结果的调用
qsort(a, low, loc - 1);
qsort(a, loc + 1, high);
}
}
int q[1111];
int r;
void up(int i)
{
int j;
while(i > 1)
{
j = i / 2;
if(q[j] > q[i]) swap(q[i], q[j]);
else break;
i = j;
}
}
void down(int i)
{
int j;
while(i * 2 <= r)
{
j = i * 2;
if(j + 1 <= r && q[j] > q[j + 1]) j++;
if(q[i] > q[j]) swap(q[i], q[j]);
else break;
i = j;
}
}
void del()
{
swap(q[1], q[r]);
r--;
down(1);
}
void insert(int x)
{
q[++r] = x;
up(r);
}
int ans[1111];
int main()
{
while(scanf("%d%d", &n, &m) != EOF)
{
r = 0;
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
qsort(a, 0, n - 1);
for(int i = n - 1; i >= 0; i--)
{
int flag = 0;
for(int j = i - 1; j >= 0 && j >= i - m; j--)
{
int x = a[i] + a[j];
if(r < m)
{
flag = 1;
insert(x);
}
else if(x > q[1])
{
flag = 1;
del();
insert(x);
}
}
if(!flag) break;
}
for(int i = 0; i < m; i++)
{
ans[i] = q[1];
del();
}
for(int i = m - 1; i > 0; i--) printf("%d ", ans[i]);
printf("%d\n", ans[0]);
}
return 0;
}
1007：水题，找规律，没用排序。
hdu 1391
1008：水题，排个序，然后输出。
hdu 2673