qiaobaaa commented 1 year ago

include

using namespace std;

int c, n; struct MyStruct { vectorse; int id; int school; int max_distance; unordered_map<int, int>record; }s[7501];

struct cmp { bool operator()(int a, int b)const { if (s[a].max_distance != s[b].max_distance) { return s[a].max_distance > s[b].max_distance; } else { return s[a].id < s[b].id; } } };

set<int, cmp>school[10]; set<int, cmp>all; unordered_map<int, int>stu; int sum; pair<int, int>sss[10];

void init(int C, int N, int mX[], int mY[]) { c = C; n = N; sum = 0; stu.clear(); all.clear(); for (register int i = 0; i < N; i++) { school[i].clear(); sss[i] = make_pair(mX[i], mY[i]); }

for (register int i = 0; i < 7501; i++)
{
    s[i].se.clear();
    s[i].record.clear();
}
return;

}

void arrange(int num) { for (auto i : s[num].se) { //按距离最近的开始遍历选择，如果还有空位置就可以直接加入 if (school[i].size() < c) { s[num].school = i; school[i].emplace(num); all.emplace(num); return; } else { //人已经满了会产生3种情况； // 1.跟最后的一名的距离都小于，把原来学校最小优先级的学生都挤不走，只能到下一轮 //2.跟最后的一名的距离相等，但是id却大于，到下一轮 //3. 跟最后的一名的距离相等，但是id却小于，把最后一名挤走 //4.比最后一名距离大，直接把最后一名挤走 int n = *school[i].rbegin(); if (s[n].max_distance == s[num].max_distance) { //3 if (s[n].id > s[num].id) { s[num].school = i; school[i].emplace(num); all.emplace(num); all.erase(n); school[i].erase(n); //按照一层一层往下推，直到全安排好 arrange(n); return; } } else if (s[n].max_distance < s[num].max_distance) { //4 s[num].school = i; school[i].emplace(num); all.emplace(num); all.erase(n); school[i].erase(n); //按照一层一层往下推，直到全安排好 arrange(n); return; } } } }

int add(int mStudent, int mX, int mY) { stu[mStudent] = sum; vector<pair<int, int>>tem; for (register int i = 0; i < n; i++) { int x = sss[i].first - mX < 0 ? mX - sss[i].first : sss[i].first - mX; int y = sss[i].second - mY < 0 ? mY - sss[i].second : sss[i].second - mY; tem.push_back(make_pair(x + y, i)); } sort(tem.begin(), tem.end()); //该同学的最远距离 s[sum].max_distance = tem.rbegin()->first; s[sum].id = mStudent; //把该同学依次最近的学校给输入进来 int g = 1; for (auto i : tem) { s[sum].se.push_back(i.second); s[sum].record[i.second] = g; g++; }

for (auto i : tem)
{
    //按距离最近的开始遍历选择，如果还有空位置就可以直接加入
    if (school[i.second].size() < c)
    {
        s[sum].school = i.second;
        school[i.second].emplace(sum);
        all.emplace(sum);
        sum++;
        return i.second;
    }
    else
    {
        //人已经满了会产生3种情况；
        // 1.跟最后的一名的距离都小于，把原来学校最小优先级的学生都挤不走，只能到下一轮
        //2.跟最后的一名的距离相等，但是id却大于，到下一轮
        //3. 跟最后的一名的距离相等，但是id却小于，把最后一名挤走
        //4.比最后一名距离大，直接把最后一名挤走
        int num = *school[i.second].rbegin();
        if (s[num].max_distance == s[sum].max_distance) //tem.rbegin()->first)
        {
            //3
            if (s[num].id > mStudent)
            {
                s[sum].school = i.second;
                //添加新的

                school[i.second].erase(num);

                all.erase(num);

                all.emplace(sum);

                school[i.second].emplace(sum);
                //删除旧的
                //按照一层一层往下推，直到全安排好
                arrange(num);

                sum++;
                return i.second;
            }
        }
        else if (s[num].max_distance < s[sum].max_distance)
        {
            //4
            s[sum].school = i.second;
            //添加新的
            school[i.second].erase(num);

            all.erase(num);

            all.emplace(sum);

            school[i.second].emplace(sum);
            //删除旧的
            //school[i.second].erase(num);
            //按照一层一层往下推，直到全安排好
            arrange(num);
            sum++;
            return i.second;
        }

    }
}

}

void brrange(int result, int pos) { //不需要移动 if (school[s[result].school].size() < c) { //把原来的删除 school[s[result].school].erase(result); //添加到新的位置

    s[result].school = pos;
    school[pos].emplace(result);
    return;

}
else
{
    //满了要移动，每次找出要移动的下一个点
    auto it = school[s[result].school].rbegin();
    int num1 = s[*it].id;
    num1 = stu[num1];

    int city = s[*it].school;

    auto it1 = all.find(result);
    it1++;

    school[s[result].school].erase(result);
    s[result].school = pos;
    school[pos].emplace(result);

    for (it1; it1 != all.end(); it1++)
    {
        //如果result的优先级是要比他现在的高，证明他就是要被移动的
        if (s[*it1].record[city] < s[*it1].record[s[*it1].school])
        {
            brrange(*it1, city);
            break;
        }
    }
}

}

int remove(int mStudent) {

int result = s[stu[mStudent]].school;
int num = stu[mStudent];
//stu.erase(mStudent);
//未满谁也不移动
if (school[result].size() < c)
{
    stu.erase(mStudent);
    school[result].erase(num);
    all.erase(num);
    return result;
}
//满了要移动，每次找出要移动的下一个点
auto it = school[result].rbegin();
int num1 = s[*it].id;
num1 = stu[num1];

auto it1 = all.find(num1);
it1++;

//删除原来的
stu.erase(mStudent);
school[result].erase(num);
all.erase(num);

for (it1; it1 != all.end(); it1++)
{
    //如果result的优先级是要比他现在的高，证明他就是要被移动的
    if (s[*it1].record[result] < s[*it1].record[s[*it1].school])
    {
        brrange(*it1, result);
        break;
    }
}
return result;

}

int status(int mSchool) { return school[mSchool].size(); }

qiaobaaa commented 1 year ago

include

using namespace std;

int C; int N; int id; struct child{ int pos; pair<int,int> sc[10];

}student[10005];

struct sch{ int x,y;

}school[10]; set<pair<int,int>>S[10], W[10]; unordered_map<int,int>sid;

void init(int C, int N, int mX[], int mY[]){ ::C=C; ::N=N; for(int i=0;i<N;i++){ school[i] = {mX[i],mY[i]}; S[i].clear(); W[i].clear();

}
sid.clear();
id =0;

} void update(int p, int mid){ int val = student[p].sc[N-1].first; for(int k=0;k<N;k++){ pair<int,int> x = student[p].sc[k]; if(S[x.second].size()<C){ student[p].pos = x.second; S[x.second].insert({-val,mid});

        return;
    }
    else{
        pair<int,int> cur = *S[x.second].rbegin();
        if(-cur.first<val || -cur.first==val && mid <cur.second){
            S[x.second].erase(cur);
            S[x.second].insert({-val,mid});
            student[p].pos = x.second;
            update(sid[cur.second],cur.second);
            return;
        }
        else{
            W[x.second].insert({-val,mid});
        }

    }

}

}

void rm_update(int p){ if(!W[p].empty()){ pair<int,int> cur = *W[p].begin(); W[p].erase(cur); int cid = sid[cur.second]; int prev = student[cid].pos; S[prev].erase(cur); S[p].insert(cur); student[cid].pos = p; rm_update(prev);

}

int add(int mStudent, int mX, int mY){ sid[mStudent]= ++id; student[id] = {}; for(int i=0;i<N;i++){ student[id].sc[i] = {abs(mX-school[i].x)+abs(mY-school[i].y),i}; } sort(student[id].sc,student[id].sc+N); update(id,mStudent); return student[id].pos; }

int remove(int mStudent){ int rid = sid[mStudent], val = student[rid].sc[N - 1].first, p = student[rid].pos; S[p].erase({ -val, mStudent }); for (int i = 0; i < N; i++) W[i].erase({ -val, mStudent }); rm_update(p); return p; } int status(int mSchool){ return S[mSchool].size(); }

qiaobaaa commented 1 year ago

set algo

qiaobaaa / response3

School Assignment #6

include

include

include

include

include

include

include

include