这是我的题解，使用不是很熟练，请多理解指正。
BY:王子豪
做题页面链接：HPU算法协会公开课第一期：【基础算法1】
A - 前m大的数
特点：考察了对时间复杂度的理解。
思路：找出开数组的关键大小；思考，如何才能快速的找到需要的目标数字，发现使用sort可以先排序然后倒着找。在sort之前用冒泡把每两个的和存起来。
注意：开数组在main之外，并且输出的时候注意最后一个数据换行！
#include<iostream>
#include<algorithm>
using namespace std;
int a[3005];//如果最大3000个数据*3000 要9百万/2 开数组是需要开一半就够了
int N,M;//初始化
int sum[5000000];//存取给出的数字的和
int main(){
while(cin>>N>>M){
for(int i=1;i<=N;i++){
scanf("%d",&a[i]);
}
int cnt=1;//记录位数 从1开始存
for(int i=1;i<=N;i++){
for(int j=i+1;j<=N;j++){
sum[cnt++]=a[i]+a[j];
}
}
sort(sum,sum+cnt);
for(int i=cnt-1,z=M;i>0;i--,z--){
if(z==1) {
printf("%d\n",sum[i]);break; }
else printf("%d ",sum[i]);
}}
return 0;
} B - 稳定排序
特点：细节上增大了一点对结构体排序的认识，引入名词“不稳定排序”，事实上大多数排序都是不稳定排序。
思路：定义结构体，正常判断。 可以用一个计数器来最终判断是不稳定排序，还是正确的。
注意：判断情况1：不稳定情况，是满足分数对应，名字不对应。
判断情况2：失败情况，分数不对应，名字也不对应。
情况3：分数名字都不对应。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct student{
int score;//成绩
int count;
char name[55];//名字
}a[350],b[350];
int cmp(student x,student y)
{
if(x.score!=y.score)
return x.score>y.score;
else
return x.count<y.count; //先返回序号在前的
}
int main()
{ //排序首先是按照分数 假定排序后 先判断名字 就可以做到是不是稳定的，如果连名字都不对
//肯定都不是正确的了 假设分数对 名字不对 就是不稳定的
int n;
while(~scanf("%d",&n))
{ //清空
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for(int i=0;i<n;i++)
{
scanf("%s %d",&a[i].name,&a[i].score);
a[i].count=i; //记录序号
}
sort(a,a+n,cmp); //正规的排序之后
int q=1,w=1; //设置变量 判断 q判断名字同样 w判断分数重
for(int i=0;i<n;i++)
{
scanf("%s %d",&b[i].name,&b[i].score);
if(strcmp(a[i].name,b[i].name)!=0) //排序之后每一个都不对应，说明可能不稳定
q=0; //名字这个不相同但是后面的人数都是对应的
if(a[i].score!=b[i].score)
w=0;
}
if(q+w==2)
printf("Right\n");
else if(q==0&&w==1) //不稳定 名字对应分数不对应
{
printf("Not Stable\n");
for(int i=0;i<n;i++)
printf("%s %d\n",a[i].name,a[i].score);
}
else //分数都不对应
{
printf("Error\n");
for(int i=0;i<n;i++)
printf("%s %d\n",a[i].name,a[i].score);
}
}
return 0;
}C - 开门人和关门人
特点：考察了结构体排序问题，加上时间转换和细节。
思路：正常排序。
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
struct person{
char name[20];
// char time[100];
int time1;
int time2;
}a[1000];
bool cmp1(person a, person b)
{
return a.time1 < b.time1;
}
bool cmp2(person a, person b)
{
return a.time2 > b.time2 ;
}
int main(){
int N,M;//记录数据
int h,m,s;//记录时：分：秒 最后换算一下
scanf("%d",&N);
while(N--){
scanf("%d",&M);
for(int i=0;i<M;i++){
scanf("%s %d:%d:%d", &a[i].name,&h,&m,&s);//按照格式输入名字时间分时秒
a[i].time1=s+m*60 + h*3600; //第一天的开始时间 用s算
scanf("%d:%d:%d",&h,&m,&s);//第一天的结束就时间
a[i].time2=s+m*60 + h*3600;
}
// 排序（按开门时间）
sort(a, a+M, cmp1);
// 输出开门人名字 找最早开门
cout << a[0].name << " ";
// 排序（按关门时间） 找最晚开门
sort(a, a+M, cmp2);
cout << a[0].name << endl;
}
return 0;
}D - EXCEL排序
特点：这里突然想到了，可以用c++中的string直接进行比较。不再使用strcmp进行返回值比较
#include<iostream>
#include<algorithm>
#include<math.h>
#include<cstring>
using namespace std;
struct student{
char number[8];
char name[10];//名字
int score;//成绩得分
}a[111111];;
//开始定义cmp
bool cmp1(student a,student b){
//在第一种比较情况下，使用字符串比较，先返回字符小的，也就是递增排序
return strcmp(a.number,b.number )<0; //这里把学号存成字符形式 不要yint的
}
bool cmp2(student a,student b){
if(strcmp(a.name ,b.name)!=0)
{
return strcmp(a.name,b.name)<0;//非递减，先返回小的
}
else
{
return cmp1(a,b);//两个名字相等 就按第一种递增的
}
}
bool cmp3(student a,student b){
if(a.score!=b.score )
{
return a.score <b.score ;
}
else
{
return cmp1(a,b);
}
}
int main(){
int i,j,n,m,count=0;
while(cin>>n>>m&&n){
for(i=0;i<n;i++){
cin>>a[i].number>>a[i].name>>a[i].score;
} //正常结构体读取
//开始判断 怎么进行排序
if(m==1){
sort(a,a+n,cmp1);
}
if(m==2){
sort(a,a+n,cmp2);
}
if(m==3){
sort(a,a+n,cmp3);
}
cout<<"Case "<<++count<<":"<<endl;
for(i=0;i<n;++i)
{
cout<<a[i].number<<" "<<a[i].name<<" "<<a[i].score;
if(i!=n)
cout<<endl;
}
}
return 0;
}F - 水果
特点：可以使用结构体，但是比较麻烦，而且不是很熟练，不如接受一个新的STL内容-> map容器
map特点：1，其基本单位（节点）为pair类型，就是必须有实值（value）和键值。pair的第一元素为键值（通过.first 或->first访问），第二元素为实值（通过.second 或者->second访问）
2，map不容许有相同的键值
3，map中的所有元素（value）都根据键值（key）被自动排序。
4，键值不可以被修改
补充：c++ 里面的map容器的迭代器里面 有个first 和 second
例如
map<string, int> m;
m["one"] = 1;
map<string, int>::iterator p = m.begin();
p->first; // 这个是 string 值是 "one"
p->second; //这个是 int 值是 1
思路：容器套容器，在一个map容器里面放入一个map容器，读取的时候采用二位数组，先读取地区，在读取水果名字，塞进去容器，自动排序。访问的时候就分别定义一，二节迭代器访问其中已经排序好的，每一个first都对应着一个储存水果类型和个数的map<string,int>。
#include <iostream>
#include <map>
#include <stdio.h>
#include <string>
using namespace std;
string s1,s2;
int main()
{
//map< string,map<string,int> >mmp;
//map<string,int>mp;
map< string,map<string,int> > p;
int t,n,num,flag = 0;
cin>>t;
while(t--){
p.clear();
cin>>n;
while(n--){
cin>>s2>>s1>>num;
p[s1][s2]+=num; //s1是地区 s2是水果种类 连带着水果种类和数量
}
map< string,map<string,int> >::iterator iter1;//地区容器+
map<string,int>::iterator iter2;//水果容器 在地区容器的第二个
for(iter1 = p.begin(); iter1!= p.end();iter1++){
cout<<iter1->first<<endl;//先输出地区 也就是第一个迭代器的最开头的一个
for(iter2 = iter1->second.begin();iter2 != iter1->second.end();iter2++){
cout<<" |----"<<iter2->first<<"("<<iter2->second<<")"<<endl;//在地区里面读取
//输出格式 并且读取
}
}
if(t){
cout<<endl;
}
}
return 0;
//fclose(stdin);
}G - 不重复数字
特点：set结构体去重，使用count查找，返回值类型是0/1.
因为set容器会直接进行排序，所以思路改变一下：把数据存入数组中，同时也存进去set，每次存入的数据都用count查找一下，如果饭hi之是0，在输出这个输入的数据，并且注意
#include<iostream>
#include<set>
#include<algorithm>
#include<stdio.h>
using namespace std;
int a[50005];
int main(){
set<int>q;
int N,m,x,z=0;
scanf("%d",&N);
while(N--){
q.clear();
scanf("%d",&m);
// int count=0;
for(int i=0;i<m;i++){
scanf("%d",&a[i]);
z=a[i]; //这里count返回值是一个证书，1代表有0无
if(q.count(z)==0){
// if(count>0) //判断是不是第一个数字
// printf(" ");
//前面的是判断的是 是不是第一位 输出空格 不是第一位的都要出一个空格
printf("%d ",z);
// count++;
q.insert(z);
}
}
printf("\n");
}
return 0;
}H - 表达式括号匹配
特点：栈典型应用。
代码1：数组模仿栈：
#include<stack>
#include<iostream>
#include<cstring>
using namespace std;
int judge(char s[]){
char stack[50000];
int top=-1;
int i;
int len=strlen(s);
for(i=0;i<len;i++){
if(s[i]=='('){
stack[++top] = '(';
}
if(s[i] == ')') {
if (top == -1) {
return 0;
}
else
--top;
}
}
if (top == -1)
return 1;
else
return 0;
}
int main(){
char s[2005];
scanf("%s",&s);
if(judge(s)){
printf("YES");
}
else
printf("NO");
} 代码二：stack
#include<iostream>
#include<stack>
#include<cstring>
using namespace std;
stack<char>st;
string s;
bool judge(){
int len=s.size();
int c=1;
for(int i=0;i<len;i++){
if(st.empty()&&s[i]==')'){
return 0;
c=0;
break;
}
if(s[i]=='('){
st.push(s[i]);
}
if(s[i]==')'&&!st.empty()){
st.pop();
}
}
if(st.empty()&&c!=0)
return 1;
else
return 0;
}
int main(){
cin>>s;
if(judge()){
printf("YES");
}
else
printf("NO");
return 0;
}I - 合并果子
思路，用queue队列中的优先队列做。
特点：priority_queue <int>q;</int>
因为合并果子是贪心算分典型，要先合并堆数字比较小的，但是优先队列是大根堆，如果压入1，2，3他会先合并2，3所以我们可以压入符数-1-22-3，这样县合并-1-2这样的话，我们就可以用减法求体力了。这是杜皓轩教给我的，谢谢他。
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
priority_queue <int>q;
int main(){
int t,n,z,sum,s;
scanf("%d",&t);
while(t--){
sum=0;
s=0;
// while (!q.empty()) q.pop();
cin>>n;
for(int i=0;i<n;i++){
cin>>z;
q.push(-z);
}
for(int i=1;i<n;i++){
s=q.top();
q.pop();
s=s+q.top();
q.pop();
q.push(s);
sum=sum-s;
}
printf("%d\n",sum);
}
return 0;
}K - Ignatius and the Princess IV
伊格内修斯和公主四世
特点：找出一组n个数据中出现次数超过（n+1）/2次数的数据，并且输出
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<cstring>
using namespace std;
const int maxn = 1e6+10;
int a[maxn],b[maxn];
int main(){
int n;
while(scanf("%d",&n)!=EOF){
memset(b,0,sizeof(b));
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
b[a[i]]++;
//cout<<b[a[i]]<<" ";
}
int count=(n+1)/2;
for(int i=0;i<n;i++){
//用的这个方法是偶然想到的 以前做过把数组开到堆里面
//所有的数组都是0，然后如果是存在一个就是1，两个就是2；
if(b[a[i]]>=count){
cout<<a[i]<<endl;
break; }
}
}
return 0;
}思路二
#include <cstdio>
#include <cstring>
#include<algorithm>
#include <iostream>
using namespace std;
int a[1000000]; int main()
{ int n;
while(scanf("%d",&n)!=EOF)
{for(int i=0;i<n;i++)
{ scanf("%d",&a[i]);}
sort(a,a+n);
printf("%d\n",a[(n+1)/2]); }
return 0;
}M - SnowWolf's Wine Shop
买酒题目，听了高手的讲解才会的，才知道有multiset这个东西。。
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
multiset<int>st;
int n,q,y;
int xu;//这是需求 每个人需要的那种价格的就睡
int main(){
int t;
scanf("%d",&t);
int count=0;
while(t--){
printf("Case %d:\n",++count);
st.clear();
scanf("%d%d%d",&n,&q,&y);
for(int i=0;i<n;i++){
int z;
scanf("%d",&z);
st.insert(z);
}
while(q--){
scanf("%d",&xu);
multiset<int>::iterator it=st.lower_bound(xu);
if(it==st.end()||*it-y>xu){
printf("-1\n");
}
else{
printf("%d\n",*it);
st.erase(it);//删除的是这个位置 用迭代器位置
}
}
}
return 0;
}
京公网安备 11010502036488号