[COCI2016-2017#5] Unija

_H17_ · 2023-10-01 16:12:51 · 题解

题目分析

其实就是告诉你边长求覆盖之后的总面积。

只需要维护 i 这么高的地方多宽即可。

70 分代码

//-O2
#include<bits/stdc++.h>
using namespace std;
unsigned int n,x,y,a[10000001];
unsigned long long ans;
int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x>>y;
        x/=2,y/=2;//其实只要维护一个角的
        int idx=upper_bound(a+1,a+n+1,y,greater<int>())-a;
        for(int i=idx;i<=x;i++)
            a[i]=max(a[i],y);//全部记录
    }
    for(int i=1;i<=10000000;i++)
        ans+=a[i];
    ans*=4;
    cout<<ans;
    return 0;
}

优化

其实分析下读入的时候需要把 idx \to x 全扫一遍，比较消耗时间。

因为我们去掉了 \frac{3}{4} 所以矩形一定是通到底的，所以只把他最高的地方记录上，然后往下的都和上一层取 \max 然后一直到最底下（我知道很难说清楚，具体看代码）。

代码

#include<bits/stdc++.h>
using namespace std;
unsigned int n,x,y,a[10000001];
unsigned long long ans;
int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x>>y;
        x/=2,y/=2;
        a[x]=max(a[x],y);//把最上面记录
    }
    for(int i=10000000;i;i--){
        a[i]=max(a[i],a[i+1]);//和上面层比较
        ans+=a[i];
    }
    cout<<ans*4;
    return 0;
}