这是我写的贪心5章中的第2章,这一章,我想讲一讲在OI竞赛中,贪心直觉的重要性
在考场上,因为考前作息,心理状态甚至生理状态,都会影响我们的成绩,所以考场上分析问题的能力可能会大有缩水,所以我认为,普及组想拿一等奖,平时至少要有提高组一等奖或二等奖的水准
不过讲这些好像跑题了,想在考场上写对贪心算法,对一个选手的要求是很高的,那么,除了可怕的数学建模能力,就真的没有解决贪心的方法了?
答案是:直觉
https://www.luogu.org/problemnew/show/P4447
也许正如那些大神所说的,在2018的安徽省选中,我只在现场AC了两题,一道红题,一道绿题(也就是上面这题),平时都能切切蓝题的,但是在考场上,T2(一道蓝题)只拿到了40分的暴力,主要就是靠这题来扳回分数
大概一个小时,拿下了T1和T2(T2写的暴力),看了一下题面,感觉这题还是可做的,于是开始苟正解
我们是用n表示总人数,a[]这个数组来表示某个队员的实力的。那么我们再把每个组里的人数放入f[]数组,num表示当前是第几个组,而用b[]数组表示某组最大的能力值。首先我们要将所有人按他们的能力值从小到大排序,然后再进行处理:
1、如果存在,也就是使b[j]+1=a[i],那么可以直接插入到J组后面(这里无需考虑是不是最大值,因为前面排过序了,所以必定为最大的),为了能让最小的人数尽可能大,那么应该插入到那个满足条件人数最少的组
2、否则a[i]不可以插入到任何一组,那么就必须新增一组
这也正是我半个小时思考后的结果,于是开始码代码,(为了防止出锅),我花费了1H写这题,因为这个问题具备单调性,所以本来准备写完T4后再加一波二分查找的,但是T4的正解好像没苟出来,于是就把这份代码交上去了(以下码风较丑,因为是考场上写的)
#include<cstdio>
#include<algorithm>
using namespace std;
int a[100005];
struct NODE{
int lr;
int ln;
}node[100005];
int main(){
//freopen ("division.in","r",stdin);
//freopen ("division.out","w",stdout);
int n;
scanf ("%d",&n);
for (int i=1;i<=n;++i){
scanf ("%d",&a[i]);
}
sort (a+1,a+1+n);
int len=1,ans=1<<30,j;
node[1].lr=a[1];node[1].ln=1;
for (register int i=2;i<=n;++i){
int find1=1<<30,find2=0;
for (j=1;j<=len;++j){
if ((a[i]-node[j].lr==1)||(a[i]-node[j].lr==-1)&&node[j].ln<find1){
find1=node[j].ln;
find2=j;
}
}
if (find1==(1<<30)){
++len;
node[len].ln=1;
node[len].lr=a[i];
}
else{
node[find2].ln++;
node[find2].lr=a[i];
}
}
for (register int i=1;i<=len;++i){
if (node[i].ln<ans) ans=node[i].ln;
}
printf ("%d\n",ans);
return 0;
}
然后,我就在考场上切了这题,这种贪心我也不会证明,但是,直觉让我写对了,全班也就两个人AC(%%%ZJFjulao)
强化直觉,就是要靠刷一些贪心来训练直觉,当然也要有数学建模的基础