d[贪心] | Hexo

归档于 2019-10-11 17:50

拉到最后就能看到我了

t1,每个矩形有长宽,可以删去m个矩形使min{长}*min{宽}最大

t1打了个假的贪心,同时以$a,b$排序,每次找到$a,b$中较小的删去,然后大样例过不了

其实自己手摸了一组也过不了

3 1

6 5

1 10000

1 10000

按照我的贪心删掉1 10000(1比较小),其实删掉6 5更优

于是很慌,又打了个假的贪心,每次找到$delta$最小的,

然后大样例又过不了…

有点崩,然后又随便打了两个贪心基本就是往上蒙贪心策略了

然后大样例依然过不了,

然后想难道这是反悔贪心,

然后就扔了

其实t1跟之前一道t2很像,和多面手那个贪心很像啊,自己没有迁移过来,罪有应得

一层循环枚举删掉多少长最小的,剩下删掉宽小的

这样一定保证贪心是正确的,这样是$n^2$,然后优化一下就$n*log(n)$了(主席树优化,二分优化,堆优化,各种优化都能过)

哈我不知道我考试时在想什么

我好傻逼啊

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 111111
ll T,n,m;
ll vis[A];
struct node{
    ll a,b,id;
    node(){}
    node(const ll &x,const ll &y,const ll &z){a=x,b=y,id=z;}
    friend bool operator < (const node &x,const node &y){
        return x.a<y.a;
    }
}p1[A];
struct node2{
    ll b;
    node2(){}
    node2(const ll &y){b=y;}
    friend bool operator < (const node2 &x,const node2 &y){
        return x.b>y.b;
    }
};
priority_queue<node2>q;
int main(){
//    freopen("d2.in","r",stdin);
//    freopen("zj.out","w",stdout);
    scanf("%lld",&T);
    while(T--){
        scanf("%lld%lld",&n,&m);
        while(q.size()) q.pop();
        for(ll i=1;i<=n;i++){
            ll x,y;
            scanf("%lld%lld",&x,&y);
            p1[i]=node(x,y,i);
        }
        sort(p1+1,p1+n+1);        
        for(ll i=m+1;i<=n;i++)
            q.push(node2(p1[i].b));
        ll maxx=0;
        for(ll i=m;i>=0;i--){
//            printf("p1[i+1].a=%lld q.top()=%lld\n",p1[i+1].a,q.top().b);
            maxx=max(p1[i+1].a*q.top().b,maxx);
            q.push(node2(p1[i].b));
            q.pop();
//            if(p1[i].b<q.top().b) continue ;//一定被删
//            else q.pop(),q.push(node2(p1[i].b));
        }
        printf("%lld\n",maxx);
    }
}

View Code