P7205 Drvca 题解

Demeanor_Roy · 2022-10-16 19:34:22 · 题解

• 原题链接

• 来一个不一样的做法。

• 考虑 n^3 暴力。首先将圣诞树按高度从小到大排序，不难想到确定高度最小的一棵圣诞树，枚举其它 n-1 棵圣诞树与它构成等差数列前两项，再贪心地能选择选，O(n) 判断剩下的圣诞树是否可行。

• 乍一看这个做法是 O(n^2) 的，可实际上每往序列贪心地加入一项后，我们都需要判断一次，而不是全部加完才判断。这是因为第一个序列不是选得越多越好，可能它中的某一个元素需要作为第二个序列的桥梁，所以需要多次判断。

• 思考如何优化？仔细观察就会发现，确定一个序列的前两项根本不需要枚举 n-1 次，根据鸽巢原理可知，用最小的三棵圣诞树就能确定一个序列的前两项。所以其实只需要判断 (1,2),(1,3),(2,3) 作为序列前两项就行了。时间复杂度降至 O(n^2)。

• 最后考虑用数据结构优化判断剩下的数能否构成等差数列的过程。我们发现每次往一个序列中贪心地加入一项，就是在另一个序列中删去一项。用链表维护被删的那个序列，同时用 STL 中的 map 维护相邻元素的差及个数，每次删去一个数就动态维护一下 map，判断能否构成等差序列就是判断第一项和第二项的差的个数是否为元素个数减一。于是时间复杂度优化到了 O(n \log n ) 。

• 细节：需要特判一下 n=2 的情况。

• 代码：

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
int n,val[N],L[N],R[N];
bool st[N];
map<int,int> mp;
inline bool check(int a,int b)
{   
    mp.clear();
    memset(L,0,sizeof L);
    memset(R,0,sizeof R);
    memset(st,0,sizeof st);
    st[a]=st[b]=true;
    int last=0,cnt=2;
    for(int i=1;i<=n;i++)
    {
        if(st[i])   continue;
        if(last)    mp[val[i]-val[last]]++;
        L[i]=last,R[last]=i;
        last=i;
    }
    if((int)mp[val[R[R[0]]]-val[R[0]]]==n-cnt-1)    return true;
    last=b;
    for(int i=1;i<=n;i++)
    {
        if(st[i]||val[i]-val[last]!=val[b]-val[a])  continue;
        if(L[i])    mp[val[i]-val[L[i]]]--;
        if(R[i])    mp[val[R[i]]-val[i]]--;
        if(L[i]&&R[i])  mp[val[R[i]]-val[L[i]]]++;
        R[L[i]]=R[i];L[R[i]]=L[i];
        cnt++;last=i;st[i]=true;
        if((int)mp[val[R[R[0]]]-val[R[0]]]==n-cnt-1)    return true;
    }
    return false;
}
inline void print()
{
    int num=0;
    for(int i=1;i<=n;i++)   if(st[i])   num++;
    printf("%d\n",num);
    for(int i=1;i<=n;i++)   if(st[i])   printf("%d ",val[i]);
    printf("\n%d\n",n-num);
    for(int i=1;i<=n;i++)   if(!st[i])  printf("%d ",val[i]);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)   scanf("%d",&val[i]);
    sort(val+1,val+n+1);
    if(n==2)    printf("1\n%d\n1\n%d",val[1],val[2]);
    else if(check(1,2)||check(1,3)||check(2,3)) print();
    else printf("-1");
    return 0;
}

• 完结撒花~