2019牛客第十场F题详解_算法日常[13/100]

发表于 更新于 分类于 阅读次数：
2019牛客第十场F题详解 贪心题 天将降大任于斯人也，必先苦其心志，劳其筋骨，饿其体肤，空乏其身，行拂乱其所为，所以动心忍性，曾益其所不能

2019牛客第十场F题详解

题目

2019牛客第十场F题详解


题解

我的分析请看代码

本来以为发现了更快更简单的做法，结果想写成思路给大家看，然后不断想怎么表述这个算法，想着想着发现这是一个假的超快AC算法，然后大家有兴趣的话可以看我的AC代码二的分析(果然写blog做搬运工也是有收获的)

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn=6e5+5;
const int N=6e5+3;
int a[maxn],b[maxn],cnt[maxn],ans,n,r;
vector <int> h[maxn];
multiset <int> s;
void add(int x){
    auto p=s.find(cnt[x]);
    s.erase(p); cnt[x]++;
    s.insert(cnt[x]);
}
void del(int x){
    auto p=s.find(cnt[x]);
    s.erase(p); cnt[x]--;
    s.insert(cnt[x]);
}
int main(){
    cin >> n >> r;
    for (int i=0;i<n;i++){
        cin >> a[i] >> b[i];
        /* 统一右移2*r */
        a[i]+=r*2; b[i]+=r*2;
    }
    for (int i=0;i<n;i++){
        /*打a[i]的时候,把a[i]-r,a[i]+r也叠加上a[i]上面的值,
        这样就能使得a[i]表示打a[i]能获得的总值*/
        h[a[i]-r].pb(b[i]);
        h[a[i]].pb(b[i]);
        h[aa[i]+r].pb(b[i]);
        cnt[b[i]]++; cnt[b[i]-r]++; cnt[b[i]+r]++;
    }
    for (int i=r;i<=N-r;i++) s.insert(cnt[i]);
    for (int i=r;i<=N-r;i++){
        /*得到中间打这里能够得到的个数*/
        int ret=(int)h[i].size();
        /*暂时删除相关的所有列值*/
        for (auto x:h[i]) del(x),del(x-r),del(x+r);
        /*然后得到当下最大的3列值*/
        auto p=s.rbegin();
        ans=max(ans,ret+(*p));
        /*再把列值插回去*/
        for (auto x:h[i]) add(x),add(x-r),add(x+r);
    }
    cout << ans << endl;
}

能更快AC的假算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/*直接行列序列化排序的做法,真滴是好想法!*/

/*2019年8月18日20:26:30 发现这是一个假做法！靠着数据水才过的！因为这里只比较了最大的3个
行值，就去比较列值了！

因为可能有一种情况就是选第4大行，但是取到的列值更多，这应该是有可能出现的，
总之这种做法虽然能过   但是是有可能遗漏情况的假算法！

必须要枚举到所有的行
*/
#include<bits/stdc++.h>
using namespace std;
const int M =1e5 + 10;
int num[M *3];
int  n , r , ans;
int cnt[M * 3];
struct node{
    int x , y;
    int id;
    bool operator<(node d)const{
        return x > d.x;
    }
}a[M] , b[M];

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >>r;
    for(int i =1;i <= n;i++){
        cin >> a[i].x >> a[i].y;
        a[i].x++;
        a[i].y++;
        num[a[i].x]++;
    }
    /*枚举每个行坐标,相加从上到下3行的值-->二维降到一维*/
    for(int i = 1;i <= 100000;i++){
        /*之所以放在最左边是因为i是从最左边开始,免去判断*/
        b[i].x = num[i] + num[i +r] + num[i +r +r];
        b[i].id = i;
    }
    /*行值获利大到小排序*/
    sort(b + 1 ,b + 100001);
    for(int i = 1;i <= 3;i++){
        memset(cnt , 0 ,sizeof(cnt));
        for(int j = 1;j <= n;j++){
            /*除去原来的行(3次行值取max)以外的其他列的值的统计*/
            if(a[j].x != b[i].id && a[j].x != b[i].id +r  && a[j].x != b[i].id +r * 2) cnt[a[j].y]++;
        }
        int sum = 0;
        for(int j = 1; j < M;j++) sum = max( sum , cnt[j] + cnt[j +r] +cnt[j + r + r]);
        ans = max(ans , sum + b[i].x);
    }
    cout << ans <<endl;
}

每天叨叨一句

天将降大任于斯人也，必先苦其心志，劳其筋骨，饿其体肤，空乏其身，行拂乱其所为，所以动心忍性，曾益其所不能