week6
- 贪心
- 6-1 三国游戏
- 6-2 独木桥
- 6-3 排队接水
- 6-4 合并果子
- *6-5 线段覆盖
- *6-6 均分纸牌
- *6-7 导弹拦截
企业建站必须是能够以充分展现企业形象为主要目的，是企业文化与产品对外扩展宣传的重要窗口，一个合格的网站不仅仅能为公司带来巨大的互联网上的收集和信息发布平台，
成都创新互联面向各种领域：
成都主动防护网等
成都网站设计公司、
全网整合营销推广解决方案、网站设计等建站排名服务。
贪心
贪心不像是一种算法，更像是一种思维方式。
对于以下习题，笔者不禁发出深深感慨：这能算贪心？
6-1 三国游戏
题目链接
LGP1199
解题思路
构造出几种情况后就能猜想到：只要保证小涵所选的武将A，能使得与武将A默契值第二大的那个数大即可。但并没有构造出计算机赢的情况，于是乎抱着骗分的心态交了前面的猜想，然后居然AC了？！
具体博弈论题解可查看洛谷。（绝对不是因为笔者太蒻看不懂QAQ
#includeusing namespace std;
const int maxn=505;
int a[maxn][maxn];
int n;
int main(){cin>>n;
for (int i=1; ifor (int j=i+1; j<=n; j++){int k;
cin>>k;
a[i][j]=k;
a[j][i]=k;
}
}
int ans=0;
for (int i=1; i<=n; i++){sort(a[i]+1,a[i]+1+n);
if (a[i][n-1] >ans){ans=a[i][n-1];
}
}
cout<<1<
6-2 独木桥
题目链接
LGP1007
解题思路
（参考了相关题解）
两者相遇均调头 等价于 两者相遇后仍按照原先位置前行。
比如一个士兵位于坐标3，方向向右，那么两秒后，不论他经过了多少士兵，都一定会有一个士兵在坐标5。
#includeusing namespace std;
const int maxn=5e3+5;
int a[maxn];
int main(){// freopen("LGP1007.in","r",stdin);
// freopen("LGP1007.out","w",stdout);
int L;
int n,k;
cin>>L;
cin>>n;
int maxn=0,minn=0;
for (int i=1; i<=n; i++){cin>>k;
maxn=max(max(L-k+1,k),maxn);
minn=max(min(L-k+1,k),minn);
}
cout<
注意：
max和min的使用要分清楚，min用于一个人两个方向上的最小值，而最后要保证所有人都要通过，所以又要取max。
6-3 排队接水
题目链接
LGP1223
解题思路
显然需要将节水时间更短的人放在前面，这样人数能更快地减少，能使得最后平均节水时长最小。
#includeusing namespace std;
const int maxn=1e3+5;
double sum,cnt;
int n;
struct node{int t;
int num;
}a[maxn];
bool cmp(node x,node y){return x.tcin>>n;
for (int i=1; i<=n; i++){scanf("%d",&a[i].t);
a[i].num=i;
// sum+=a[i];
}
sort(a+1,a+1+n,cmp);
for (int i=1; i<=n; i++){cnt+=a[i].t*(n-i);
}
for (int i=1; i<=n; i++){printf("%d ",a[i].num);
}
printf("\n%.2lf",double(cnt)/n);
//system("pause");
return 0;
}
6-4 合并果子
题目链接
LGP1090
解题思路
显然每次要先将和最小的两组合并，这样的结果才是最优的。数据较大，需要用priority_queue进行每次首元素的读取和push。同时注意开long long。
#includeusing namespace std;
typedef long long ll;
priority_queue, greater>q;
const int maxn=1e4+5;
int n;
ll ans;
int main(){cin>>n;
int k;
for (int i=1; i<=n; i++){scanf("%d",&k);
q.push(k);
}
while (q.size()>1){ll tmp;
tmp=q.top();
q.pop();
tmp+=q.top();
q.pop();
q.push(tmp);
ans+=tmp;
}
cout<
彩蛋：
如果要求合并的两组要相连，就是需要用区间DP的合并石子了。
*6-5 线段覆盖
题目链接
LGP1803
解题思路
贪心思想，对于每个时间段都可视为一个线段，那么尽可能去使得线段右端点越小越好。这样对于后面的线段选择与否影响更小，故必然就是最优解。
#includeusing namespace std;
int n;
struct node{int l,r;
};
vectort;
bool cmp(node a,node b){return (a.rcin>>n;
for (int i=0; inode tmp;
cin>>tmp.l>>tmp.r;
t.push_back(tmp);
}
sort(t.begin(),t.end(),cmp);
int lt=-1,ans=0;
for (int i=0; iif (t[i].l >= lt){ans++;
lt=t[i].r;
}
}
cout<
本题可以不用vector笔者只是单纯想来练习其使用
注意vector的使用：
1.vector与结构体结合使用时，要注意读入的时候，需要用一个node tmp，读到tmp中，再a.push_back(tmp)即可；
2.push_back是从0开始的，所以之后调用应注意从0到n-1；
3.vector排序：sort(a.begin(),a.end(),cmp).
*6-6 均分纸牌
题目链接
LGP1031
解题思路
对于2~N-1的纸牌堆，都可以选择移动到左边或右边，这样两个方向较难进行模拟。所以可视为都向右边移动，并且移动的牌数可以为负数（相当于原本向左移动纸牌），如果当前牌数达到了平均值就continue，否则就把多的数值或者少的数值移动给右边的纸牌堆。
#includeusing namespace std;
const int maxn=1e2+5;
int a[maxn];
int main(){int n;
cin>>n;
int sum=0;
for (int i=1; i<=n; i++){cin>>a[i];
sum+=a[i];
}
int ave=sum/n;
int cnt=0;
for (int i=1; i<=n; i++){if (a[i]!=ave){a[i]-=ave;
a[i+1]+=a[i];
cnt++;
}
}
cout<
*6-7 导弹拦截
题目链接
LGP1020
解题思路
这题并不是原题普通的LIS，需要将时间复杂度降为O(nlogn)，并且还要计算该序列中LIS的最小个数。
对于问题一，可以用二分进行优化。f[cnt]表示该LIS中有cnt个数时最后一个数字的大高度。对于每一个a[i]进行判断，如果a[i]小于当前大序列的最后一个数字高度，那么就可以cnt++，并将f[cnt]赋值为a[i]；否则，如果大于当前大序列的最后一个数字高度，就需要从前面的序列去寻找，即存在一个f[x]，x为1到cnt中某个数，能使得f[x]大于a[i]，同时f[x+1]小于a[i]，那么f[x+1]就是当前a[i]需要加入的序列。
对于问题二，很类似问题一，也可以用二分进行优化。f[cnt]表示第cnt个系统中最小导弹的高度，同时保证f[ ]数组的单调递增，也就是f[1]到f[cnt]都是单增的。那么对于每一次的a[i]都可以进行判断，如果a[i]大于f[cnt]，也就是没有系统拦截当前的导弹，就需要f[++cnt]=a[i]；反之，如果小于，那就二分寻找合适的高度。
#includeusing namespace std;
const int maxn=1e5+5;
vectora;
int n;
int f[maxn],v[maxn];
int main(){int k;
while (scanf("%d",&k)!=EOF){a.push_back(k);
}
n=a.size();
memset(f,0x3f,sizeof(f));
int cnt=0;
for (int i=0; iif (a[i]<=f[cnt]){f[++cnt]=a[i];
}
else {int l=1,r=cnt;
while (1){int mid=l+r>>1;
if (f[mid]>=a[i] && f[mid+1]break;
}
if (f[mid]>=a[i]){l=mid+1;
}
else if (f[mid]r=mid-1;
}
}
int mid=l+r>>1;
f[mid+1]=a[i];
}
}
memset(f,0,sizeof(f));
int ans=0;
for (int i=0; iif (a[i]>f[ans]){f[++ans]=a[i];
}
else {int l=1,r=ans;
while (1){int mid=l+r>>1;
if (f[mid]=a[i]){break;
}
if (f[mid]>=a[i]){r=mid-1;
}
else if (f[mid]l=mid+1;
}
}
int mid=l+r>>1;
f[mid+1]=a[i];
}
}
cout<
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
网页名称：week6(贪心)-创新互联
文章位置：
http://cdkjz.cn/article/eidss.html
