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; }