程序设计与算法 | (22) Lecture(11) OJ作业

OJ地址

Lecture (11)包含以下五道编程题，可以在上面的OJ提交。

062:sort简单题

#include <iostream>
#include <algorithm>
using namespace std;int main()
{
    int a[8] = {
    6,5,14,23,2,9,87,10 };sort(
a+1,a+7,greater<int>()
);for(int i = 0;i < 8; ++i)cout << a[i] << "," ; return 0;
}

063:还是sort简单题

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;struct Point{
    int x;int y;
};
struct Rule1
{
    bool operator()(const int& i1,const int& i2)const{
    if(i1%10!=i2%10)return i1%10-i2%10<0;elsereturn i1-i2>0;}
};struct Rule2
{
    bool operator()(const Point& p1,const Point& p2)const{
    int d1 = p1.x*p1.x+p1.y*p1.y;int d2 = p2.x*p2.x+p2.y*p2.y;if(d1 != d2)return d1-d2<0;else{
    if(p1.x!=p2.x){
    return p1.x-p2.x<0;}else{
    return p1.y-p2.y<0;}}}
};
int main()
{
    int a[8] = {
    6,5,55,23,3,9,87,10 };sort(a,a+8,Rule1());for(int i = 0;i < 8; ++i)cout << a[i] << "," ;cout << endl;Point ps[8] = {
    {
    1,0},{
    0,1},{
    0,-1},{
    -1,0},{
    1,-1},{
    1,1},{
    2,0},{
    -2,0} } ;sort(ps,ps+8,Rule2());for(int i = 0;i < 8; ++i)cout << "(" << ps[i].x << "," << ps[i].y << ")";return 0;
}

064:Set

#include <iostream>
using namespace std;
#include <set>int main(int argc, const char * argv[]) {
    multiset<int> mst; //可以有重复元素 存储基本类型int元素，默认从小到大排序set<int> st; //没有重复元素int n;char cmd[10];cin>>n;int d;while(n--){
    cin>>cmd>>d;if(cmd[1]=='d')  //add{
    mst.insert(d);st.insert(d);cout<<mst.count(d)<<endl; //count函数用于统计 集合中等于d（==：按照当前排序规则，该元素必须排在d前不成立，d必须排在该元素前不成立）的元素个数}else if(cmd[1]=='e') //del{
    cout<<mst.count(d)<<endl;mst.erase(d); //删除集合中等于d的所有元素}else    //ask{
    set<int> ::iterator i = st.find(d);if(i!=st.end())cout<<1<<" "<<mst.count(d)<<endl;elsecout<<0<<" "<<0<<endl;}}return 0;
}

065:热血格斗场

#include <iostream>
using namespace std;
#include <map>
#include <cmath>int main(int argc, const char * argv[]) {
    map<int,int> mp;  //map自动按照first排序 默认从小到大；按first查询，包括二分查找，lower_bound,upper_bound.int n;mp.insert(make_pair(1e9, 1));//实力值为first id为second 实力值互不相同，没有重复用mapint power,id;scanf("%d",&n);map<int,int>::iterator i;while(n--){
    scanf("%d%d",&id,&power);   //数据量比较大时，用scanf、printf输入输出 比cin、cout快很多，后者会超时。i = mp.upper_bound(power); //返回指向 map中 first>power（按照当前的排序规则，该元素first必须排在power后面）的下标最小的那个元素。if(i==mp.end()){
    i--;printf("%d %d\n",id,i->second);}else{
    if(i==mp.begin()) //map中只有一个元素printf("%d %d\n",id,i->second);else{
    int tmp1 = abs(i->first-power);i--;int tmp2 = abs(i->first-power);if(tmp2<=tmp1)printf("%d %d\n",id,i->second);else{
    i++;printf("%d %d\n",id,i->second);}}}mp.insert(make_pair(power, id));}return 0;
}

066:冷血格斗场

//这道题目 的实力值可以有重复；我们需要把重复问题转换为非重复问题，就可以和上个题目一样求解了。
#include <iostream>
using namespace std;
#include <map>
#include <cmath>int main(int argc, const char * argv[]) {
    map<int,int> mp;  //map自动按照first排序 默认从小到大；按first查询，包括二分查找，lower_bound,upper_bound.int n;mp.insert(make_pair(1e9, 1));//实力值为first id为second 实力值互不相同，没有重复用map 或者mp[power]=id 即mp[1e9]=1int power,id;scanf("%d",&n);map<int,int>::iterator i;while(n--){
    scanf("%d%d",&id,&power);   //数据量比较大时，用scanf、printf输入输出 比cin、cout快很多，后者会超时。i = mp.upper_bound(power); //返回指向 map中 first>power（按照当前的排序规则，该元素first必须排在power后面）的下标最小的那个元素。if(i==mp.end()){
    i--;printf("%d %d\n",id,i->second);}else{
    if(i==mp.begin()) //map中只有一个元素printf("%d %d\n",id,i->second);else{
    int tmp1 = abs(i->first-power);int id1 = i->second;i--;int tmp2 = abs(i->first-power);int id2 = i->second;if(tmp2<tmp1)printf("%d %d\n",id,id2);else if(tmp2>tmp1){
    printf("%d %d\n",id,id1);}else{
    printf("%d %d\n",id,id1>id2?id2:id1);}}}i = mp.find(power);if(i!=mp.end()) //如果之前有这个实力值 则把id更新为较小的那个;把重复问题 转换为非重复问题。{
    if(id<i->second)i->second=id;}elsemp.insert(make_pair(power, id)); //或者 mp[power] = id;}return 0;
}