一.AcWing算法学习

1.区间和并

①pair<int,int>的排序优先排序左边，再排序右边；

②for(auto a:b)中b为一个容器，效果是利用a遍历并获得b容器中的每一个值，但是a无法影响到b容器中的元素。

for(auto &a:b)中加了引用符号，可以对容器中的内容进行赋值，即可通过对a赋值来做到容器b的内容填充。

#include <bits/stdc++.h>using namespace std;
typedef pair<int,int> PII;
vector<PII> segs;
const int N=1e5+10;int n;
void merge(vector<PII>&segs)
{vector<PII>res;sort(segs.begin(),segs.end());int l=INT_MIN,r=INT_MIN;for(auto item:segs){if(r<item.first){if(l!=INT_MIN)res.push_back({l,r});l=item.first;r=item.second;}else r=max(r,item.second);}if(l!=INT_MIN)res.push_back({l,r});segs=res;	
}
int main()
{int n;cin>>n;while(n--){int l,r;scanf("%d%d",&l,&r);segs.push_back({l,r});}merge(segs);cout<<segs.size();return 0;
}

2.单链表（用数组来模拟）

结构体＋指针的链表在面试中常考，但是在笔试中不常用；因为nwe Node()非常慢！

 

二.oj训练赛

1.直播获奖；

题目链接信息学奥赛一本通（C++版）在线评测系统

正常算法，每次都排序，超时，需要优化排序方法；

优化：观察样例说明发现分数是自然从大到小排列，并且都在0到600分之间，所以我们可以人为的从600到0遍历，事先记录好每个成绩出现的次数，当满足分数线计划时，输出分数线即可；

#include <bits/stdc++.h>using namespace std;
const int N=1e5+10;int n,w;int a[605];
int main()
{cin>>n>>w;for(int i=1;i<=n;i++){int x;scanf("%d",&x);a[x]++;int sum=0;for(int j=600;j>=0;j--){sum+=a[j];int t=i*w/100;int maxx=max(1,t);if(sum>=maxx){cout<<j<<' ';break;}}}return 0;
}

1.sort默认是升序排列，若需降序：sort(a,a+n,greater<int>()); 

2.公交换乘；

我写的就是超时了，在一个大盒子里找票；

优化：一张优惠券也就45分钟内有效，所以最多才能存45张，以此出发，进行优化

源代码：

#include <bits/stdc++.h>using namespace std;
const int N=1e5+10;int n,k=0,sum=0;int p[N],t[N];
int main()
{cin>>n;for(int i=0;i<n;i++){int way,pi,ti,flag=0;scanf("%d%d%d",&way,&pi,&ti);if(way==0){p[k]=pi;t[k]=ti;k++;sum+=pi;}else{for(int j=0;j<k;j++){if(p[j]>=pi&&ti-t[j]<=45){flag=1;p[j]=0;t[j]=0;break;}}if(flag==0)sum+=pi;}}cout<<sum;return 0;
}

优化：找票的循环中，更新j开始找的位置，从过期的下一个开始找；

#include <bits/stdc++.h>using namespace std;
const int N=1e5+10;int n,k=0,sum=0,m=0;int p[N],t[N];
int main()
{cin>>n;for(int i=0;i<n;i++){int way,pi,ti,flag=0;scanf("%d%d%d",&way,&pi,&ti);if(way==0){p[k]=pi;t[k]=ti;k++;sum+=pi;}else{for(int j=m;j<k;j++){if(p[j]>=pi&&ti-t[j]<=45){flag=1;p[j]=0;break;}else if(ti-t[j]>45)m=j+1;}if(flag==0)sum+=pi;}}cout<<sum;return 0;
}