题解：CF2252C Risky Tower

· · 题解

向出题人喷火！为什么卡我线段树的常！

浪费 30min 导致没过 E，我已急哭。

线段树做法太 sb 了故略去。

考虑从上往下推，维护一个 set，每次贪心的用最大的来实施破坏，于是就是带删求前多少大的和可以超过询问的值。

考虑到横斩一行是一个另类的解，于是操作次数必然不多于 m，所以我们剪枝一下每次至多枚举前 m 大。

时间复杂度 O(n^2\log n)，和线段树一个复杂度但是能过。

int a[1000005];
vector<pair<int,int>>ve[1000005];
inline void solve(){
    map<int,int>mp;
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    ve[i].clear(),cin>>a[i];
    set<pair<int,int>>s;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        int x;
        cin>>x;
        mp[x]++;
        s.insert({-x,mp[x]});
        ve[i].push_back({-x,mp[x]});
    }
    int ans=m;
    for(int i=1;i<=n;i++){
        int qwq=0,sum=0;
        for(pair<int,int>j:s){
            sum-=j.first;
            qwq++;
            if(sum>=a[i])break;
            if(qwq>m)break;
        }
        if(sum>=a[i])ans=min(ans,qwq);
        for(pair<int,int>i:ve[i])
        s.erase(i);
    }
    cout<<ans<<'\n';
}
// 幸福从非泡影 以笑容证明
// 交汇的光与影 答案落定覆上姓名
// 为了你唱下去 为你将希冀传递
// 歌声将你我紧系

// 最黯淡的一个 梦最为炽热
// 万千孤单焰火 让这虚构灵魂鲜活
// 至少在这一刻 热爱不问为何
// 存在为将心声响彻

// 多少岁月想要伴你走过
// 燕回春野 蝉鸣夏夜
// 说予我