12&13：STL
Standard Template Library
sort, binary_search/lower_bound/upper_bound, multiset, set, multimap, map.
作业
1.sort简单题
Description：程序填空，产生指定输出结果。
#include <iostream>
#include <algorithm>
using namespace std; int main()
{
int a[] = {,,,,,,, };
sort(
// Your Code Here
);
for(int i = ;i < ; ++i)
cout << a[i] << "," ;
return ;
}
Input：（无）
Output：6,87,23,14,9,5,2,10,
Sample Input：（无）
Sample Output：6,87,23,14,9,5,2,10,
a+, a+, greater<int>()
2.还是sort简单题
Description：程序填空，产生指定输出结果。
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std; struct Point{
int x;
int y;
};
// Your Code Here
int main()
{
int a[] = {,,,,,,, };
sort(a,a+,Rule1());
for(int i = ;i < ; ++i)
cout << a[i] << "," ;
cout << endl;
Point ps[] = {{,},{,},{,-},{-,},{,-},{,},{,},{-,} } ;
sort(ps,ps+,Rule2());
for(int i = ;i < ; ++i)
cout << "(" << ps[i].x << "," << ps[i].y << ")";
return ;
}
Input：（无）
Output：
10,23,3,55,5,6,87,9,
(-1,0)(0,-1)(0,1)(1,0)(1,-1)(1,1)(-2,0)(2,0)
整数按照个位数从小到大排。个位数相同，则大的排前面。点按照离原点从近到远排。距离相同，则按x坐标从小到大排。x坐标也相同，则按y坐标从小到大排。
Sample Input：（无）
Sample Output：
10,23,3,55,5,6,87,9,
(-1,0)(0,-1)(0,1)(1,0)(1,-1)(1,1)(-2,0)(2,0)
struct Rule1 {
bool operator() (const int &n1, const int &n2) {
if(n1% != n2%)
return (n1%) < (n2%);
else
return n1 > n2;
}
};
double distance(Point p)
{
return sqrt(p.x*p.x+p.y*p.y);
}
struct Rule2 {
bool operator() (const Point &p1, const Point &p2) {
if(abs(distance(p1)-distance(p2)) < 1e-) {
if(p1.x != p2.x)
return p1.x < p2.x;
else
return p1.y < p2.y;
}
else
return distance(p1) < distance(p2);
}
};3.点集的查询
Description：先给定平面上一些点的坐标 然后给定一些查询命令，根据查询命令输出Yes或No，要求使用sort和binary_search实现。
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
struct Point
{
int x;
int y;
}points[];
bool func(const Point & P1,const Point & p2);
struct Rule {
bool operator () ( const Point & p1,const Point & p2) {
return func(p1,p2);
}
};
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i = ;i < n; ++i)
scanf("%d%d",&points[i].x, &points[i].y);
// Your Code Here
Input：
第一行是整数n和m，0<n，m<=100000。接下来是n行，每行两个整数x，y代表一个点的坐标。0<x，y<=10^9。
数据确保对于任意两点 (x1,y1)和(x2,y2)表达式x1>x2 && y1<y2 || x1<x2 && y1>y2一定为真。
再接下来是m行，每行格式为x n或y n，分别表示询问x坐标为n的点是否存在和y坐标为n的点是否存在。 0<n<=10^9。
Output：对每个询问，输出 "Yes"或"No"。
Sample Input：
5 6
8 22
12 20
5 24
13 19
2 30
x 12
x 7
y 20
y 7
y 19
x 8
Sample Output：
Yes
No
Yes
No
Yes
Yes
sort(points, points+n, Rule());
for(int i=; i<m; ++i) {
int a;
char cmd[];
scanf("%s %d", cmd, &a);
Point pt;
if(cmd[] == 'x') {
pt.x = a;
if(binary_search(points, points+n, pt, Rule()))
printf("Yes\n");
else
printf("No\n");
}
else {
pt.x = -;
pt.y = a;
if(binary_search(points, points+n, pt, Rule()))
printf("Yes\n");
else
printf("No\n");
}
}
return ;
} bool func(const Point &p1, const Point &p2)
{
if(p1.x!=- && p2.x!=-)
return p1.x < p2.x;
else
return p1.y > p2.y;
}
4.set
Description：
现有一整数集（允许有重复元素），初始为空。我们定义如下操作：
add x 把x加入集合；del x 把集合中所有与x相等的元素删除；ask x 对集合中元素x的情况询问。对每种操作，我们要求进行如下输出：
add 输出操作后集合中x的个数；del 输出操作前集合中x的个数；ask 先输出0或1表示x是否曾被加入集合（0表示不曾加入），再输出当前集合中x的个数，中间用空格格开。
Input：第一行是一个整数n，表示命令数。0<=n<=100000。后面n行命令，如Description中所述。
Output：共n行，每行按要求输出。
Sample Input：
7
add 1
add 1
ask 1
ask 2
del 2
del 1
ask 1
Sample Output：
1
2
1 2
0 0
0
2
1 0
#include <iostream>
#include <cstdio>
#include <set>
#include <string>
#include <cstring> using namespace std; typedef multiset<int>::iterator PTR; int main()
{
int n;
multiset<int> mst;
set<int> st;
PTR p;
scanf("%d", &n); for(int i=; i<n; ++i) {
char cmd[];
int x;
scanf("%s %d", cmd, &x);
switch(cmd[]) {
case 'd':
st.insert(x);
mst.insert(x);
printf("%d\n", mst.count(x));
break;
case 'e':
printf("%d\n", mst.count(x));
p = mst.find(x);
if(p != mst.end()) {
pair<PTR,PTR> range = mst.equal_range(x);
mst.erase(range.first, range.second);
}
break;
case 's':
set<int>::iterator pp = st.find(x);
if(pp != st.end())
printf("1 %d\n", mst.count(x));
else
printf("0 %d\n", mst.count(x));
break;
}
} return ;
}
5.热血格斗场
Description：
为了迎接08年的奥运会，让大家更加了解各种格斗运动，facer新开了一家热血格斗场。格斗场实行会员制，但是新来的会员不需要交入会费，而只要同一名老会员打一场表演赛，证明自己的实力。我们假设格斗的实力可以用一个正整数表示，成为实力值。另外，每个人都有一个唯一的id，也是一个正整数。为了使得比赛更好看，每一个新队员都会选择与他实力最为接近的人比赛，即比赛双方的实力值之差的绝对值越小越好，如果有两个人的实力值与他差别相同，则他会选择比他弱的那个（显然，虐人必被虐好）。不幸的是，Facer一不小心把比赛记录弄丢了，但是他还保留着会员的注册记录。现在请你帮facer恢复比赛纪录，按照时间顺序依次输出每场比赛双方的id。
Input：
第一行一个数n(0 < n <=100000)，表示格斗场新来的会员数（不包括facer）。以后n行每一行两个数，按照入会的时间给出会员的id和实力值。一开始，facer就算是会员，id为1，实力值1000000000。输入保证两人的实力值不同。
Output：N行，每行两个数，为每场比赛双方的id，新手的id写在前面。
Sample Input：
3
2 1
3 3
4 2
Sample Output：
2 1
3 2
4 2
#include <iostream>
#include <set>
#include <cstdio>
#include <cmath> using namespace std; struct Fighter
{
int id;
int power;
};
struct Rule
{
bool operator()(const Fighter &f1, const Fighter &f2) {
return f1.power < f2.power;
}
}; int main()
{
int n;
scanf("%d", &n);
set<Fighter, Rule> st;
Fighter ft;
ft.id = ;
ft.power = ;
st.insert(ft);
for(int i=; i<n; ++i) {
scanf("%d %d", &ft.id, &ft.power);
set<Fighter>::iterator pl = st.lower_bound(ft);
set<Fighter>::iterator pu = st.upper_bound(ft);
if(pl == st.begin())
printf("%d %d\n", ft.id, pl->id);
else if(pu == st.end()){
--pu;
printf("%d %d\n", ft.id, pu->id);
}
else {
--pl;
if(ft.power-pl->power <= pu->power-ft.power)
printf("%d %d\n", ft.id, pl->id);
else
printf("%d %d\n", ft.id, pu->id);
}
st.insert(ft);
} return ;
}
6.冷血格斗场
Description：
为了迎接08年的奥运会，让大家更加了解各种格斗运动，facer新开了一家冷血格斗场。格斗场实行会员制，但是新来的会员不需要交入会费，而只要同一名老会员打一场表演赛，证明自己的实力。我们假设格斗的实力可以用一个正整数表示，成为实力值，两人的实力值可以相同。另外，每个人都有一个唯一的id，也是一个正整数。为了使得比赛更好看，每一个新队员都会选择与他实力最为接近的人比赛，即比赛双方的实力值之差的绝对值越小越好，如果有多个人的实力值与他差别相同，则他会选择id最小的那个。不幸的是，Facer一不小心把比赛记录弄丢了，但是他还保留着会员的注册记录。现在请你帮facer恢复比赛纪录，按照时间顺序依次输出每场比赛双方的id。
Input：
第一行一个数n(0 < n <=100000)，表示格斗场新来的会员数（不包括facer）。以后n行每一行两个数，按照入会的时间给出会员的id和实力值。一开始，facer就算是会员，id为1，实力值1000000000。
Output：N行，每行两个数，为每场比赛双方的id，新手的id写在前面。
Sample Input：
3
2 3
3 1
4 2
Sample Output：
2 1
3 2
4 2
#include <iostream>
#include <cstdio>
#include <map>
#include <cmath> using namespace std; multimap<int, int> mp; void toErase(multimap<int, int>::iterator p1, multimap<int, int>::iterator p2)
{
if(p1->first == p2->first) {
if(p1->second < p2->second)
mp.erase(p2);
else
mp.erase(p1);
}
} int main()
{
mp.insert(make_pair(,));
int n;
scanf("%d",&n); for(int i=; i<n; ++i) {
int id, power;
scanf("%d %d",&id, &power);
multimap<int,int>::iterator p = mp.insert(make_pair(power,id));
multimap<int,int>::iterator pL = p; -- pL;
multimap<int,int>::iterator pR = p; ++ pR;
if(p == mp.begin()) {
printf("%d %d\n",id, pR->second);
toErase(p,pR);
}
else if(p == --mp.end()) {
printf("%d %d\n", id, pL->second);
toErase(p,pL);
}
else {
int dL = abs(p->first-pL->first);
int dR = abs(p->first-pR->first);
if(dL<dR || dL==dR && pL->second<pR->second) {
printf("%d %d\n", id, pL->second);
toErase(p,pL);
}
else if(dL>dR || dL==dR && pL->second>pR->second) {
printf("%d %d\n", id, pR->second);
toErase(p,pR);
}
}
} return ;
}
#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>
#include <set>
#include <algorithm> using namespace std; map<int,set<int> > mp; int main()
{
set<int> st;
st.insert();
mp.insert(make_pair(, st));
int n;
scanf("%d", &n); for(int i=; i<n; ++i) {
int id,power;
scanf("%d %d",&id, &power);
map<int,set<int> >::iterator pL = mp.lower_bound(power);
if(pL == mp.end())
printf("%d %d\n", id, *(mp.rbegin()->second.begin()));
else if(pL == mp.begin())
printf("%d %d\n", id, *(mp.begin()->second.begin()));
else {
if(pL->first == power)
printf("%d %d\n", id, *(pL->second.begin()));
else {
int d1 = abs(pL->first-power);
map<int,set<int> >::iterator p = pL;
--p;
int d2 = abs(p->first-power);
if(d1 < d2)
printf("%d %d\n", id, *(pL->second.begin()));
else if(d1 > d2)
printf("%d %d\n", id, *(p->second.begin()));
else {
printf("%d %d\n", id, min(*(pL->second.begin()), *(p->second.begin())));
}
}
}
mp[power].insert(id);
} return ;
}