HPU算法协会公开课第一期：【基础算法1】(做题经验)
A-前m大的数
话说这道题之前就做过，当时是因为开的数组太小，然后就错了。
解题过程
我尝试了一种新的方法（虽然是错的，但是能发现错的原因也挺好）：
先把数组从大到小排序 也就是 7 6 5 4 3 2 1 从前往后加，但是忽然发现有点难以实现，比如如果按 7+6 7+5 7+4，，，，，，6+5 6+4 ，，这样循环，你会发现 7+3 < 6+5 所以还是按部就班吧，先求 和数组 再排序 记得数组要开的大一点，（5e5差不多）
具体看代码：
#include<cstdio>
#include<algorithm>
using namespace std;
int sum[5000000];
int a[3050];
int main()
{
int n,m,i,j,k;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=0;i<n;i++)
scanf("%d",&a[i]);
k=0;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
sum[k]=a[i]+a[j];
k++;
}
}
sort(sum,sum+k);
for(i=k-1;i>k-m;i--)
printf("%d ",sum[i]);
printf("%d\n",sum[k-m]);
}
return 0;
} B - 稳定排序｜｜ C - 开门人和关门人 ｜｜ D - EXCEL排序
由于这三道题都是一个知识点 ，就合并了
这题一看就是结构体排序呀，用sort()函数排就行,重点就是自定义函数 cmp() 的定义
看代码：
//B
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int maxn=1000;
typedef long long ll;
int n;
struct student{
string name;
int score;
int num;
}a[maxn],na[maxn];
bool cmp(student a,student b){
if(a.score != b.score) return a.score > b.score;
return a.num < b.num;
}
int main()
{
ios;
while(cin>>n){
for(int i=0;i<n;i++){
cin>>a[i].name>>a[i].score;
a[i].num=i;
}
sort(a,a+n,cmp);
bool flag=1,flag1=1;
for(int i=0;i<n;i++) {
cin>>na[i].name>>na[i].score;
if(a[i].score != na[i].score) flag =0;
else if(a[i].name != na[i].name) flag1 =0;
}
if(flag==0){
cout<<"Error"<<"\n";
for(int i=0;i<n;i++) cout<<a[i].name<<" "<<a[i].score<<"\n";
}
else if(flag==1 && flag1 == 0){
cout<<"Not Stable"<<endl;
for(int i=0;i<n;i++) cout<<a[i].name<<" "<<a[i].score<<"\n";
}
else if(flag && flag1) cout<<"Right"<<"\n";
}
return 0;
}
//C
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int maxn=1e4+10;
typedef long long ll;
int n;
struct student{
string num;
string begin;
string end;
}a[maxn];
bool cmp(student a,student b){
return a.begin < b.begin;
}
bool cmp1(student a,student b){
return a.end > b.end;
}
int main()
{
ios;
int t;
cin>>n;
while(n--){
cin>>t;
for(int i=0; i<t; i++){
cin >> a[i].num >> a[i].begin >>a[i].end;
}
sort(a,a+t,cmp);
cout<<a[0].num<<" ";
sort(a,a+t,cmp1);
//if(n>=1)
cout<<a[0].num<<"\n";
//else cout<<a[0].num;
}
return 0;
}
//D
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int maxn=1e5+10;
typedef long long ll;
int n,c;
struct student{
string num;
string name;
int score;
}a[maxn];
bool cmp(student a,student b){
if(c==1){
return a.num < b.num;
}
else if(c==2){
if(a.name == b.name){
return a.num < b.num;
}
else return a.name < b.name;
}
else{
if(a.score == b.score){
return a.num < b.num;
}
else return a.score < b.score;
}
}
int main()
{
ios;
int Case=1;
while(cin>>n>>c && n){
for(int i=0; i<n; i++){
cin>>a[i].num>>a[i].name>>a[i].score;
}
sort(a,a+n,cmp);
cout<<"Case "<< Case++ <<":"<<"\n";
for(int i=0;i<n;i++) cout<<a[i].num<<" "<<a[i].name<<" "<<a[i].score<<"\n";
}
return 0;
}E - {A} + {B}
本来应该用set做的，但是 STL 用的还不熟练（虽然知道这样不好），但还是用数组做了：
解体思路：先把两个数组合并，再用unique去重（不知道unique的小伙伴点这里）
unique
感觉也挺简单的。
代码如下：
#include<iostream>
#include<algorithm>
#include<string.h>
const int MAX=1000000;
int a[MAX],b[MAX],sum[MAX];
using namespace std;
int main()
{
int n,m;
while(cin>>n>>m){
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<m;i++){
cin>>b[i];
}
int x=n+m;
for(int i=0;i<x;i++){
if(i<n){
sum[i]=a[i];
}
else{
sum[i]=b[i-n];
}
}
sort(sum,sum+x);
long long int y=unique(sum,sum+x)-sum;
for(int i=0;i<y;i++){
if(i<y-1){
cout<<sum[i]<<" ";
}
else{
cout<<sum[i];
}
}
cout<<endl;
}
return 0;F - 水果
这道题挺绕的（第一次做的时候真的不知道咋做，还好这是第二次）
这道题用map嵌套可以做，但是我还没有完全理解，就不多赘述：
我用的还是结构体排序，麻烦了点，但挺好理解的：
看代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct aa
{
char c1[81],c2[81];
int n;
}a[115];
bool camp(aa x,aa y)
{
if(strcmp(x.c1,y.c1)!=0)
return strcmp(x.c1,y.c1)<0;
return strcmp(x.c2,y.c2)<0;
}
int main ()
{
int i,t,n,sum;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
getchar();
for(i=1;i<=n;i++)
scanf("%s %s %d",a[i].c2,a[i].c1,&a[i].n);
sort(a+1,a+n+1,camp);
strcpy(a[0].c1,"00");
strcpy(a[0].c2,"00");
a[0].n=-1;
strcpy(a[n+1].c1,"00");
strcpy(a[n+1].c2,"00");
a[n+1].n=-1;
sum=a[1].n;
for(i=1;i<=n;i++)
{
if(strcmp(a[i].c1,a[i-1].c1)!=0)
{
printf("%s\n",a[i].c1);
}
if(strcmp(a[i].c1,a[i+1].c1)==0&&strcmp(a[i].c2,a[i+1].c2)==0)
{
sum+=a[i+1].n;
}
else
{
printf(" |----%s(%d)\n",a[i].c2,sum);
sum=a[i+1].n;
}
}
if(t)
printf("\n");
}
return 0;
}G - 不重复数字
思路：用map存一下，一个一个判断，重复的元素不输出就好
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<set>
#include<map>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int MAXN = 50000 + 10;
int read()
{
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f *= -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
map<int, int> st;
int n, x;
int main()
{
int t = read();
while(t--)
{
n = read();st.clear();bool flag = true;
for(int i=0;i<n;i++)
{
x = read();
if(st[x] == 0)
{
if(!flag) printf(" ");
printf("%d", x);
flag = false;
}
st[x] = 1;
}
printf("\n");
}
return 0;
}H - 表达式括号匹配
栈模版题：把左括号放进栈里，遇见右括号就弹出一个，如果最后栈不为空，或者栈为空了但是还有右括号，就不匹配，否则就匹配：
代码如下：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<stack>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int maxn = 1e6+10;
typedef long long ll;
char a[3000];
int main()
{
bool flag=1;
stack <char> s;
cin>>a;
int len = strlen(a);
//cout<<len<<endl;
for(int i=0;i<len;i++){
if(s.size()){
if(a[i]==')'){
s.pop();
continue;
}
}
else{
if(a[i]==')'){
cout<<"NO";
flag=0;
break;
}
}
if(a[i]=='('){
s.push(a[i]);
}
}
if(flag==1 && !s.size()){
cout<<"YES";
}
else if(flag==1 && s.size()){
cout<<"NO";
}
return 0;
}I - 合并果子
要使耗费的精力最少，那么就要每次合并最小的两堆：
代码如下：
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int a[1001];
int main()
{
int t;
cin>>t;
int n;
while(t--){
int sum=0;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<n-1;){
int b=0;
sort(a+i,a+n);
b=a[i]+a[i+1];
sum+=b;
a[++i]=b;
//cout<<sum<<endl;
}
cout<<sum<<endl;
}
return 0;
}K - Ignatius and the Princess IV
这道题是求中位数把，一个数出现了（n+1）/2次 超过一半了，中位数肯定有它
看代码：
//#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<set>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int maxn=1e6+10;
typedef long long ll;
int n;
int a[maxn];
int main()
{
ios;
while(cin>>n){
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);
if(n & 1){
cout<<a[(n+1)/2]<<"\n";
}
else cout<<(a[n/2]+a[n/2+1])/2<<"\n";
}
return 0;
}M - SnowWolf's Wine Shop
这道题用multiset做，里面有一个lowerbound()函数返回集合里第一个大于等于参数元素的位置(返回值是地址，第一次就卡在了这里，学习的时候还是要认真一些)
那思路不就是：按照顺序，如果酒价和客人付的钱相差不超过某一个值，输出这个值，否则输出-1；
代码如下：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<set>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int maxn=1e6+10;
typedef long long ll;
int a,b,c,m;
int main()
{
ios;
int t,j=1;
cin>>t;
while(t--){
multiset<int> w;
w.clear();
cin>>a>>b>>c;
cout<<"Case "<<j++<<":"<<"\n";
for(int i=0 ; i<a; i++){
cin>>m;
w.insert(m);
}
for(int i=0; i<b; i++){
cin>>m;
if(w.lower_bound(m)==w.end()||*w.lower_bound(m)-m > c){
cout<<"-1"<<"\n";
}
else{
cout<<*w.lower_bound(m)<<"\n";
w.erase(w.lower_bound(m));
}
}
}
return 0;
}N - Alice, Bob and Candies
一直又都点讨厌这种模拟题，真的好麻烦
理解都写在代码的注释上了，看看吧，
//#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<set>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int maxn=1e6+10;
typedef long long ll;
int const N=2e5+5;
int c[N];
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&c[i]);
n--;
int a=0,b=0,u=0,cnt=0; //a存Alice吃的糖数，b存储Bob吃的糖数
//u存储上一次某人吃的糖数，cnt表示轮数。
for(int i=0;i<=n;)
{
cnt++;
int sum=c[i++]; //sum表示这次某人吃的糖数
while(sum<=u&&i<=n) sum+=c[i++]; //算出吃几堆才能大于上次的
a+=sum;
u=sum;
if(i>n) break; //判断糖是否全被a吃完了，是则停止
cnt++;
sum=c[n--]; //因为是从右往左枚举，所以可以通过n--来操作
while(sum<=u&&i<=n) sum+=c[n--];
b+=sum;
u=sum;
}
printf("%d %d %d\n",cnt,a,b); //最后输出即可
}
return 0;
}
P - Max Sum
最大子区间和：
早就研究过这个问题，也做过类似的题，第一次做的题是单单求最大子区间的和，但是没有问他的下标，我做完的时候给他加了这个功能，但是没有去评测，谁知道竟然是错的！！！
不过看了问了同学储存下标的思路，立马就懂了：
思路如下：
定义一个 当前的最大值，还有一个 最大的最大值，如果 当前的最大值 *大于 *最大的最大值，
更新 最大的最大值 ，还有一个技巧，就是，如果当前的最大值是负数的话，它这个负值对结果就造成了影响，所以令thissum=0,再从下一个元素加起；
代码如下：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<set>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int maxn=1e6+10;
typedef long long ll;
int n;
int a[maxn];
int main()
{
ios;
int t,Case=1;
cin>>t;
while(t--){
cin>>n;
int s=1,e=1,te=1;
int thissum=0,maxsum=-maxn;
for(int i=1;i<=n;i++){
cin>>a[i];
thissum+=a[i];
if(thissum > maxsum){
s=te;
e=i;
maxsum=thissum;
}
if(thissum<0){
thissum=0;
te= i+1;
}
}
cout<<"Case "<<Case++<<":"<<"\n";
cout<<maxsum<<" "<<s<<" "<<e<<"\n";
if(t>=1) cout<<"\n";
}
return 0;
}
查看16道真题和解析
