题解 P1571 【眼红的Medusa】
引领天下
2017-10-26 21:21:44
看到楼下好多神奇的算法，觉得我这个简简单单的方法也挺好的。
我是什么算法？
说白了就是：
# 暴搜！
但是，纯暴搜是肯定要超时的，所以我们要加一个小小的优化：
规则是这样的：
设a为科技创新奖，b为特殊贡献奖。
如果a[i]>b[j],那么a[i+1]也必定大于b[j]（我用的是升序排序），之后同理。
所以，出现这种情况时，j可以毫不犹豫地向后加，一直加到b[j]不小于a[i]为止。
然后判断一不一样就可以了。
这就是一个很简单，却很实用的优化，可以AC。
代码：
```cpp
#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;
}
```
~~ PS：已经被莫名禁言3个多月了，那个路过的管理员能不能解一下啊QAQ ~~