题解 P1571 【眼红的Medusa】

看到楼下好多神奇的算法，觉得我这个简简单单的方法也挺好的。

我是什么算法？

说白了就是：

暴搜！

但是，纯暴搜是肯定要超时的，所以我们要加一个小小的优化：

规则是这样的：

设a为科技创新奖，b为特殊贡献奖。

如果a[i]>b[j],那么a[i+1]也必定大于b[j]（我用的是升序排序），之后同理。

所以，出现这种情况时，j可以毫不犹豫地向后加，一直加到b[j]不小于a[i]为止。

然后判断一不一样就可以了。

这就是一个很简单，却很实用的优化，可以AC。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,b[100005];//b的含义已经解释过
struct Node{
    int s,id;//s为选手编号，id为出现位置
}a[100005];//a见上面
//由于最后的输出顺序很坑（被坑了2次20分QAQ），所以要保留原顺序，开结构体。
inline bool cmp1(Node a,Node b){return a.s<b.s;}//排序依据1：按编号升序排
inline bool cmp2(Node a,Node b){return a.id<b.id;}//排序依据2：按在a中出现位置升序排
int main(){
    scanf ("%d%d",&n,&m);
    for (int i=0;i<n;i++)scanf ("%d",&a[i].s),a[i].id=i;//读入，标记好位置
    for (int i=0;i<m;i++)scanf ("%d",&b[i]);
    sort (a,a+n,cmp1);//排序
    sort (b,b+m);
    int i=0,j=0;
    for (;i<n;i++){
        while (b[j]<a[i].s&&j<m)j++;//优化，找最小的不比a[i]小的b[i]
        if (b[j]!=a[i].s)a[i].s=0;//不一样就标记一下不是双奖
    }
    sort (a,a+n,cmp2);//排回去
    for (i=0;i<n;i++)if (a[i].s)printf ("%d ",a[i].s);//有值才输出
    return 0;
}