176 - A. 學測分發問題

domen111

Problem: http://toj.tfcis.org/oj/pro/176/
AC: http://toj.tfcis.org/oj/chal/9187/


先依照學生的志願把學生填進去第一志願學校，如果某校名的學生數量超過正取總額，就把備取順序較後面的學生填到他的第二志願，依此類推。

[C++] 純文本查看 復制代碼

#include<iostream>
#include<map>
#include<queue>
#include<algorithm>
#define endl '\n'
using namespace std;
int n,m;
struct school{
    map<int,int> s2r; //student to rank, rank=-1:正取, 0:落榜, >0:備取順序
    priority_queue<pair<int,int>> stu; //錄取學生 first:rank second:stu id
    int count; //正取上限人數
}sch[60];
struct student{
    vector<int> gn; //志願順序
    int real; //錄取第幾志願
}stu[100100];
void procstu(int si) //把學生填入志願 si:student id
{
    student &s=stu[si];
    int goal=s.real+1;
    while(goal<s.gn.size())
    {
        school &gch=sch[s.gn[goal]];
        int mrank=gch.s2r[si];
        if( mrank!=0 && (gch.stu.size() < gch.count || mrank < gch.stu.top().first) )
        {
            gch.stu.push(make_pair(mrank,si));
            s.real=goal;
            if(gch.stu.size()>gch.count)
            {
                stu[gch.stu.top().second].real=-1;
                int tmp=gch.stu.top().second;
                gch.stu.pop();
                procstu(tmp);
            }
            return;
        }
        goal++;
    }
    s.real=-1;
}
int main()
{
    ios::sync_with_stdio(0);
    //cin.tie(0);

    int T;
    cin>>T;
    while(T--)
    {
		//input
        cin>>n>>m;
        fill_n(sch,m+5,school());
        fill_n(stu,n+10,student());
        for(int i=1;i<=n;i++)
        {
            int t;
            cin>>t;
            stu[i].gn.resize(t);
            for(int j=0;j<t;j++)
                cin>>stu[i].gn[j];
            stu[i].real=-1;
        }
        for(int i=1;i<=m;i++)
        {
            int a,b;
            cin>>a>>b;
            sch[i].count=a;
            for(int j=0;j<b;j++)
            {
                int t;
                cin>>t;
                if(j<a)
                    sch[i].s2r[t]=-1;
                else
                    sch[i].s2r[t]=j-a+1;
            }
        }
		//solve
        for(int i=1;i<=n;i++)
            procstu(i);
		//output
        for(int i=1;i<=n;i++)
        {
            int t=stu[i].real;
            if(t==-1)cout<<-1<<endl;
            else cout<<stu[i].gn[t]<<endl;
        }
    }
}