Map与对象关系的思考之P1563玩具谜题

P1563 玩具谜题

结论：

map在一些情况有种“对象”的意味，在JSON中，对象可以用K-V格式存储；mybatis中参数是map或者对象都可以实现解析。。。k-v格式的数据存储和对象可以相互转换。

使用map进行模拟

耗时1300ms。。。。不会优化了。。。，代码没精简，凑合看吧，其中if判断可以简写两两在一起，这里不改了。也不是主要要说的。

	int rolenum,ordernum;

    cin>>rolenum>>ordernum;

    map<string,int>maping;

    int direction;

    string name;

    int bushu;

    vector<string> roles;

    roles.resize(rolenum);

    for (int i = 0; i < rolenum; ++i) {

        cin>>direction>>name;

        maping[name]=direction;//0表示朝向圈内,1表示朝向圈外

        roles[i]=name;

    }

    int index = 0;//当前位置

    for (int i = 0; i < ordernum; ++i) {

        cin>>direction>>bushu;

        if(direction==0){// 表示向左数s人

            //判断当前人的朝向

            if(maping[roles[index]]==0){//0表示朝向圈内

                index-=bushu;

                index<0? index=roles.size()-abs(index) : index ;

            } else{//1表示朝向圈外

                index+=bushu;

                index<roles.size()? index: index = abs(index)-roles.size();

            }

        }else{//表示向右数s人

            //判断当前人的朝向

            if(maping[roles[index]]==0){//0表示朝向圈内

                index+=bushu;

                index<roles.size()? index: index = abs(index)-roles.size();

            } else{//1表示朝向圈外

                index-=bushu;

                index<0? index=roles.size()-abs(index) : index ;

            }

        }

    }

    cout<<roles[index];

对象模拟

这里把由map存储的方向信息设置在对象中，取消了map。

耗时位200ms，emmmm？？？提升了5倍，这想不通啊。。。将vector替换位数组后，耗时也是200+，所以没有重新分配（因为先resize了）内存块的情况下，vector和int数组增查的时间复杂度都是O（1）的

C++ map的实现是treemap，TreeMap的增删改查和统计相关的操作的时间复杂度都为 O(logn)，N*log（N）耗时1000ms么。。。差距这么直观的吗。。。。

#include <iostream>

#include <algorithm>

#include <map>

#include <vector>

#include <ctime>

using namespace std;

static const auto y = []() {

    std::ios::sync_with_stdio(false);

    std::cin.tie(nullptr);

    return 0;

}();

class Person{

public:

    int direction;//0表示朝向圈内,1表示朝向圈外

    string name;//姓名

    Person(int direction, const string &name) : direction(direction), name(name) {}

    Person() {}

};

vector<Person> roles;

void fun3(){

    int rolenum,ordernum;

    cin>>rolenum>>ordernum;

    roles.resize(rolenum);

    for (int i = 0; i < rolenum; ++i) {

        cin>>roles[i].direction>>roles[i].name;

    }

    int direction,bushu;

    int index = 0;

    for (int i = 0; i < ordernum; ++i) {

        cin>>direction>>bushu;

        if(direction==0){// 表示向左数s人

            //判断当前人的朝向

            if(roles[index].direction==0){//0表示朝向圈内

                index-=bushu;

                index<0? index=roles.size()-abs(index) : index ;

            } else{//1表示朝向圈外

                index+=bushu;

                index<roles.size()? index: index = abs(index)-roles.size();

            }

        }else{//表示向右数s人

            //判断当前人的朝向

            if(roles[index].direction==0){//0表示朝向圈内

                index+=bushu;

                index<roles.size()? index: index = abs(index)-roles.size();

            } else{//1表示朝向圈外

                index-=bushu;

                index<0? index=roles.size()-abs(index) : index ;

            }

        }

    }

        cout<<roles[index].name;

}

int main(){

    fun3();

    return 0;

}

巴特西

Map与对象关系的思考之P1563玩具谜题

使用map进行模拟

对象模拟

最新文章

热门文章