备战蓝桥杯---数据结构与STL应用（进阶2）

本文将主要围绕有关map的今典应用展开：

下面我用图进行分析：

下面为AC代码：

#include<bits/stdc++.h>
using namespace std;
struct Point
{int x,y;bool operator < (const Point & r) const {return x < r.x || ( x == r.x && y < r.y );//升序排列}
};
multiset<Point> S;
int main()
{int T, kas = 0; scanf("%d",&T);while(T--){if(kas) puts("");int n;scanf("%d",&n);printf("Case #%d:\n",++kas);S.clear();while(n--){Point P;scanf("%d%d",&P.x,&P.y);auto it = S.lower_bound(P);if(it == S.begin() || (--it)->y > P.y){it = S.insert(P);while(it != S.end() && (it->x==P.x&&it->y==P.y)) it++;while(it != S.end() && it->y >= P.y) S.erase(it++);}printf("%d\n",S.size());}}return 0;
}

接题：

其实与上一章的task题类似，我们按敌方防御力从大到小，选择攻击力合适的，在其中，如果他们防御力均小于，我们选一个防御力min的去同归于尽，反之选一个最接近敌方攻击力的。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
struct node{int att,de;
}t[100010],e[100010];
int T,n,m,k;
bool cmp(node a,node b){return a.att>b.att;
}
bool cmp1(node a,node b){return a.de>b.de;
}
int main(){cin>>T;while(T--){if(k!=0) puts(" ");scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d%d",&t[i].att,&t[i].de);for(int i=1;i<=m;i++) scanf("%d%d",&e[i].att,&e[i].de);sort(t+1,t+n+1,cmp);sort(e+1,e+m+1,cmp1);int j=1,cnt=0,f=0;map<int,int> mp;for(int i=1;i<=m;i++){while(t[j].att>=e[i].de){if(mp.count(t[j].de)==0) mp[t[j].de]=1;else mp[t[j].de]++;j++;}if(mp.empty()){f=1;break;} map<int,int>::iterator it=mp.lower_bound(e[i].att);if(it==mp.end()||(--mp.end())->first<=e[i].att){cnt++;if(--mp[mp.begin()->first]==0) mp.erase(mp.begin()->first);}else{if(it->first==e[i].att){if(--mp[(++it)->first]==0) mp.erase(it->first);}else{if(--mp[(it)->first]==0) mp.erase(it->first);}}}if(f==0) printf("Case #%d: %d",++k,n-cnt);else printf("Case #%d: -1",++k);}
}