题解 P1640 【[SCOI2010]连续攻击游戏】

· · 题解

竟然没有O(n)贪心？除本题解外唯一一篇贪心题解是O(n \log n)的。

本人不会二分图，因此看到此题就想到了一个贪心解法。

yy一个大致思路：由于必须从小到大做，不难想到我们要优先保存下标较小的点。因为最终答案肯定\leq n的，所有属性值>n的所有数都没有贡献。因此我们可以开一个桶，把所有权值\leq n的点全部丢到桶里，然后从小到大贪心。

如何贪心呢？我们定义较小点为一对数中较小的那个，较大点为较大的那个。

由于是从小到大进行的贪心，如果当前遍历的下标有能够被选取的较大点，那么他肯定跟前面的一个未被选取的较小点相匹配，我们直接无脑选即可。

若一个点是较小点，那么就需要考虑如何选才能够使得接下来的选取能够使答案最大。一开始我的贪心思路是选择下标尽量大的对应点肯定最优。但是当下标较小的较大点数量大，而下标较大的较大点数量小的时候，这种贪心策略就可能会把下标大的较大点选完，导致答案变小。You are hacked!

但是这样的hack情况给了我们启发：我们应该选择较大点数量多的地方作为答案。因此我们可以尽量选取对应较大点 所在的位置里 较大点数量最多 的那个较小点，在数量相同的时候再进行上面的那个贪心（选择尽量大的下标），这样就可以保证最优了。（有点绕，请务必认真理解这句话）

至于具体实现，对于较大点，由于是无脑选，我们不需要知道他的对应点，直接开一个桶记录就好了；而较小点，我们可以对于每个下标开一个vector，计算的时候直接暴力算就好了。

时间复杂度O(n)，其实相当于桶排了一下，因此省去了一只log。

代码

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

#define dd ch=getchar()
inline int read()
{
    int x=0;char dd;bool f=false;
    while(!isdigit(ch))f|=ch=='-',dd;
    while(isdigit(ch))x=(x<<1)+(x<<3)+ch-48,dd;
    return f?-x:x;
}
#undef dd
void write(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x>9)write(x/10);
    putchar(x%10+48);
}
#define writeln(x) (write(x),putchar('\n'))
#define writesp(x) (write(x),putchar(' '))

const int N=1000005;

int n;
vector<int>xxl[N];
int cnt[N];
int main()
{
    n=read();
    for(int i=1,x,y;i<=n;i++)
    {
        x=read(),y=read();
        if(x>y)swap(x,y);
        cnt[y]++;
        xxl[x].push_back(y);
    }
    int ans=n;
    for(int i=1;i<=n;i++)
    {
        if(cnt[i])
        {
            cnt[i]--;
            continue;
        }
        if(!xxl[i].size()){ans=i-1;break;}
        int res=xxl[i][0];
        for(int j=1;j<(int)xxl[i].size();j++)
            if(cnt[xxl[i][j]]>cnt[res]||(cnt[xxl[i][j]]==cnt[res]&&xxl[i][j]>res))
                res=xxl[i][j];
        cnt[res]--;
    }
    writeln(ans);
    return 0;
}