题解：P11533 [NOISG 2023 Finals] Topical

linjinkun · 2025-10-21 14:16:31 · 题解

和楼下一样，模拟赛有这道题然后就被吊打了。

感谢 StayAlone 的题解给我的灵感。

很显然创建一个二维数组 a，a_{i,j} = [p_j>a_{i,j}]，然后在每次维护能够新完成的测试，去完成它，由于 p_j 增大后，会修改 j 列上连续一段的值，又因为 p_j 单调不降，那每一列只需要按照值排序保证每个位置只会修改一次复杂度即可正确。

时间复杂度 O(nk \log n)，瓶颈在排序。

代码：

#include<bits/stdc++.h>
using namespace std;
namespace fast_IO {
#define FASTIO
#define IOSIZE 100000
    char ibuf[IOSIZE], obuf[IOSIZE];
    char *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#ifdef ONLINE_JUDGE
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#endif//fread in OJ, stdio in local

#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
    template<typename T> inline T read() {
        T s = 0;
        int w = 1;
        char ch;
        while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1;
        if (ch == EOF) return false;
        while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar();
        return s * w;
    }
    template<typename T> inline bool read(T &s) {
        s = 0;
        int w = 1;
        char ch;
        while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1;
        if (ch == EOF) return false;
        while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar();
        return s *= w, true;
    }
    inline bool read(char &s) {
        while (s = getchar(), isspace(s));
        return true;
    }
    inline bool read(char *s) {
        char ch;
        while (ch = getchar(), isspace(ch));
        if (ch == EOF) return false;
        while (!isspace(ch)) *s++ = ch, ch = getchar();
        *s = '\000';
        return true;
    }
    template<typename T> inline void print(T x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) print(x / 10);
        putchar(x % 10 + 48);
    }
    inline void print(char x) {
        putchar(x);
    }
    inline void print(char *x) {
        while (*x) putchar(*x++);
    }
    inline void print(const char *x) {
        for (int i = 0; x[i]; ++i) putchar(x[i]);
    }
    inline bool read(std::string& s) {
        s = "";
        char ch;
        while (ch = getchar(), isspace(ch));
        if (ch == EOF) return false;
        while (!isspace(ch)) s += ch, ch = getchar();
        return true;
    }
    inline void print(std::string x) {
        for (int i = 0, n = x.size(); i < n; ++i)
            putchar(x[i]);
    }
    template<typename T, typename... T1> inline int read(T& a, T1&... other) {
        return read(a) + read(other...);
    }
    template<typename T, typename... T1> inline void print(T a, T1... other) {
        print(a);
        print(other...);
    }

    struct Fast_IO {
        ~Fast_IO() {
            fwrite(obuf, p3 - obuf, 1, stdout);
        }
    } io;
    template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) {
        return read(b), io;
    }
    template<typename T> Fast_IO& operator << (Fast_IO &io, T b) {
        return print(b), io;
    }
#define cout io
#define cin io
#define endl '\n'
}
using namespace fast_IO;
const int N = 1e6+5;
long long p[N];
int cnt[N];
int id[N];
vector<pair<int,int>>w[N];
vector<int>v[N];
signed main()
{
    int n,k;
    cin >> n >> k;
    for(int i = 1;i<=k;++i)
    {
        w[i].resize(n+1);
    }
    for(int i = 1;i<=n;++i)
    {
        v[i].resize(k+1);
        for(int j = 1;j<=k;++j)
        {
            cin >> w[j][i].first;
            w[j][i].second = i;
        }
    }
    for(int i = 1;i<=n;++i)
    {
        for(int j = 1;j<=k;++j)
        {
            cin >> v[i][j];
        }
    }
    for(int i = 1;i<=k;++i)
    {
        sort(w[i].begin()+1,w[i].begin()+n+1);
    }
    int ans = 0;
    while(1)
    {
        int flag = 0;
        for(int i = 1;i<=k;++i)
        {
            while(id[i]<n&&w[i][id[i]+1].first<=p[i])
            {
                if(++cnt[w[i][++id[i]].second] == k)
                {
                    flag = 1;
                    ++ans;
                    int x = w[i][id[i]].second;
                    for(int j = 1;j<=k;++j)
                    {
                        p[j]+=v[x][j];
                    }
                }
            }
        }
        if(!flag)
        {
            break;
        }
    }
    cout << ans;
    return 0;
}