Swordsman(多个优先队列)

2018-08-15

Swordsman

题意

给你一个n,代表有n个队伍，一个k，代表每个队伍中有k个战士，对应k个经验值，我方队伍中也有k个战士。

输入我方战士的k个战斗力，

接下来每一行输入敌方每个队伍k个战士的战斗力，打败k个战士后可以得到的经验值。

只有我方k个战士的战斗力均对应大于敌方某个队伍中k个战士的战斗值，才能得到相应的k个经验，提升战斗力，然后接着跟其他的队伍打。

问你我方战士每个人最后最多能为多少战斗力？

k<=5,n<=1e5，保证得到的战斗力在int范围内。

思路

首先由于读入数据大，先来个读入挂。

然后我们可以对每一种敌方战士（列），建立k个优先队列，以战斗值小为上。

然后不断循环，每次从第1个战士开始和第1个队列中的敌方战士打，如果强于他，就弹出这个战士，并记录这个战士对应的队伍中的战败情况，一旦他们的队伍全军覆没，我方每个战士就可以得到相应的经验值，然后和第i个队列中的战士打，一直到i=k为止，结束一轮循环。

然后一直循环直到某一次循环中不再有打赢他们的情况出现。

看！代码

#include <bits/stdc++.h>
using namespace std;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >a[6];
namespace IO {
    const int MX = 4e7; //1e7 占用内存 11000kb
    char buf[MX]; int c, sz;
    void begin() {
        c = 0;
        sz = fread(buf, 1, MX, stdin);//一次性全部读入
    }
    inline bool read(int &t) {
        while (c < sz && buf[c] != '-' && (buf[c] < '0' || buf[c] > '9')) c++;
        if (c >= sz) return false;//若读完整个缓冲块则退出
        bool flag = 0; if(buf[c] == '-') flag = 1, c++;
        for(t = 0; c < sz && '0' <= buf[c] && buf[c] <= '9'; c++) t = t * 10 + buf[c] - '0';
        if(flag) t = -t;
        return true;
    }
}
int n,k,x,d[6],b[100008][6],c[100008]; //d用来存当前战斗力，b是打败的奖励，c是记录某一行的打败情况
pair<int,int>zz;
int main()
{
    cin.tie(0);
    cout.tie(0);
    int t;
    IO::begin();
    IO::read(t);
    while(t--)
    {
        IO::read(n);
        IO::read(k);
        memset(c,0,sizeof(c));
        for(int i=1;i<=k;i++) IO::read(d[i]);
        for(int i=1;i<=k;i++)
        {
            while(a[i].size()) a[i].pop();
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=k;j++) IO::read(x),zz.first=x,zz.second=i,a[j].push(zz); //先把所有的情况放到优先队列中
            for(int j=1;j<=k;j++) IO::read(b[i][j]);
        }
        int ans=0;
        bool f;
        while(true)
        {
            f=0;
            for(int i=1;i<=k;i++)    //对于每一列
            {
                while(!a[i].empty()) //对于某一列的最小的元素
                {
                    zz=a[i].top();
                    if(zz.first<=d[i])  //可以打败
                    {
                        a[i].pop();
                        c[zz.second]++;  //记录下这一行的打败情况
                        if(c[zz.second]==k) //如果这一行都打败了 ，就吃掉啦
                        {
                            for(int j=1;j<=k;j++) d[j]+=b[zz.second][j];
                            ans++,f=1;
                        }
                    }
                    else break;
                }
            }
            if(!f) break; //如果某次循环中没有能吃的，就break了
        }
        cout<<ans<<endl;
        for(int i=1;i<=k;i++)
        {
            if(i==1) cout<<d[i];
            else cout<<" "<<d[i];
        }
        puts("");
    }
    return 0;
}