目錄
Everyday English
前言
洛谷 P1031 均分紙牌
題目描述
思路點(diǎn)撥
AC代碼
洛谷 P1094 紀(jì)念品分組
題目描述
樣例輸入
樣例輸出?
思路點(diǎn)撥
AC代碼
洛谷 P2660 zzc 種田?
題目描述
思路點(diǎn)撥
AC Code
結(jié)尾
Everyday English
Don't miss the opportunity.
機(jī)不可失，時(shí)不再來(lái)。
前言
這節(jié)課是貪心算法的習(xí)題課，我們會(huì)講解三道題目。
貪心算法1：貪心算法第一節(jié)課
洛谷 P1031 均分紙牌
題目網(wǎng)址：[NOIP2002 提高組] 均分紙牌 - 洛谷
題目描述
有?N?堆紙牌，編號(hào)分別為?1,2,……,N。每堆上有若干張，但紙牌總數(shù)必為?N?的倍數(shù)?？梢栽谌我欢焉先∪舾蓮埣埮?，然后移動(dòng)。
移牌規(guī)則為：在編號(hào)為?1?堆上取的紙牌，只能移到編號(hào)為?2?的堆上；在編號(hào)為?N?的堆上取的紙牌，只能移到編號(hào)為?N?1?的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上。
現(xiàn)在要求找出一種移動(dòng)方法，用最少的移動(dòng)次數(shù)使每堆上紙牌數(shù)都一樣多。
例如?N=4?時(shí)，4堆紙牌數(shù)分別為?9,8,17,6。
移動(dòng)?3 次可達(dá)到目的：
- 從第三堆取?4 張牌放到第四堆，此時(shí)每堆紙牌數(shù)分別為?9,8,13,10。
- 從第三堆取?3 張牌放到第二堆，此時(shí)每堆紙牌數(shù)分別為?9,11,10,10。
- 從第二堆取?1?張牌放到第一堆，此時(shí)每堆紙牌數(shù)分別為?10,10,10,10。
思路點(diǎn)撥
首先，我們得知道每堆牌應(yīng)有多少?gòu)?。題目保證了總牌數(shù)是堆數(shù)的倍數(shù)，那么最終每一堆的牌數(shù)應(yīng)該是(a[1]+a[2]+……+a[N])/N，也就是N堆牌的平均數(shù)。
比如有4堆牌，分別是有2、3、4、7張，而平均數(shù)就是4，也就是最后每堆牌所分得的張數(shù)。
每一堆牌的張數(shù)只可能有三種情況：
1.比平均值?。荷賻讖垼妥層疫叺囊欢呀o幾張。
2.和平均值相同：不需要給，判斷下一個(gè)。
3.比平均值大：多幾張，就把多的給右邊。
情況一時(shí)，右邊一堆的張數(shù)可能會(huì)出現(xiàn)負(fù)數(shù)，但沒(méi)有關(guān)系，最終還是會(huì)有其他堆補(bǔ)回來(lái)的。
AC代碼
#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
int n,a[maxn],cnt;
int main()
{
int mean,sum=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum+=a[i];
}
mean=sum/n; //☆總和÷堆數(shù)=平均每堆牌數(shù)
for(int i=1;i<=n-1;i++)
{
if(a[i]!=mean)
{
a[i+1]+=a[i]-mean;//a[i]少的話會(huì)加上負(fù)數(shù)，相當(dāng)于減少右邊的牌
cnt++;
}
}
cout<<cnt<<endl;
return 0;
}
洛谷 P1094 紀(jì)念品分組
題目網(wǎng)址：[NOIP2007 普及組] 紀(jì)念品分組 - 洛谷?
題目描述
元旦快到了，校學(xué)生會(huì)讓樂(lè)樂(lè)負(fù)責(zé)新年晚會(huì)的紀(jì)念品發(fā)放工作。為使得參加晚會(huì)的同學(xué)所獲得的紀(jì)念品價(jià)值相對(duì)均衡，他要把購(gòu)來(lái)的紀(jì)念品根據(jù)價(jià)格進(jìn)行分組，但每組最多只能包括兩件紀(jì)念品， 并且每組紀(jì)念品的價(jià)格之和不能超過(guò)一個(gè)給定的整數(shù)。為了保證在盡量短的時(shí)間內(nèi)發(fā)完所有紀(jì)念品，樂(lè)樂(lè)希望分組的數(shù)目最少。
你的任務(wù)是寫(xiě)一個(gè)程序，找出所有分組方案中分組數(shù)最少的一種，輸出最少的分組數(shù)目。
樣例輸入
100
9
90
20
20
30
50
60
70
80
90樣例輸出?
6思路點(diǎn)撥
相信各位都學(xué)過(guò)首尾配對(duì)吧，比如計(jì)算下面這道題：
1+2+3+4+5+6+7+8+9
除了利用公式計(jì)算，我們還可以首尾配對(duì)，觀察首和尾，很容易想到1+9=10，而總共有4組余下一個(gè)5，即4×10+5=45。
而這一題要盡可能的平均不就是首尾配對(duì)嗎？但要注意一點(diǎn)，不能超過(guò)給定范圍。
既然要首尾配對(duì)，首先得排個(gè)序吧，這就要用到我們學(xué)過(guò)的sort函數(shù)了。
接著我們分析一下樣例，先把樣例排序一下：
20?20?30?50?60?70?80?90 90?
利用配對(duì)的思想：最小+最大=20+90=110，超過(guò)了限制，也就是說(shuō)，最大的只能單獨(dú)一個(gè)組。
再次利用配對(duì)的思想：最小+第二大=20+90=110，還是大了，第二大也只能單獨(dú)一組。
再次利用配對(duì)的思想：最小+第三大=20+80=100，沒(méi)有超過(guò)限制，可以為一組。
再次利用配對(duì)的思想：第二小+第四大=20+70=90，沒(méi)有超過(guò)限制，可以為一組。
以此類推，我們便可得出答案。
而模擬兩邊不斷往里縮小范圍的不就是指針嗎！上代碼！
AC代碼
#include<bits/stdc++.h>
using namespace std;
int n, w, ans;
int a[30010];
int main()
{
cin>>w>>n;
for (int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);//要想配對(duì)，先排序
int i=1,j=n;//i,j為兩個(gè)指針
while(i<=j)
{
if (a[i]+a[j]<=w)//兩個(gè)紀(jì)念品可以為一組
{
i++;
j--;
ans++;
}
else//最大單獨(dú)為一組
{
j--;
ans++;
}
}
cout<<ans<<endl;
return 0;
}
洛谷 P2660 zzc 種田?
題目網(wǎng)址：zzc 種田 - 洛谷
題目描述
田地是一個(gè)巨大的矩形，然而 zzc 每次只能種一個(gè)正方形,而每種一個(gè)正方形時(shí) zzc 所花的體力值是正方形的周長(zhǎng)，種過(guò)的田不可以再種，zzc 很懶還要節(jié)約體力去泡妹子，想花最少的體力值去種完這塊田地，問(wèn)最小體力值。
思路點(diǎn)撥
很明顯的一道貪心題，要想耗費(fèi)力氣最小，肯定是每次劃分盡可能大的正方形。
比如2×2的一個(gè)田地，如果你劃分成4個(gè)1×1的需要周長(zhǎng)：1×4×4=16cm
而劃分成1個(gè)2×2的只需要周長(zhǎng)：2×4=8cm
所以，貪心策略是：每次劃分盡可能大的正方形。?
對(duì)于3×5的正方形，最省力氣的劃分如下：
注意：最大的正方形應(yīng)該已較短的一條邊作為邊長(zhǎng)。
90分?
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
signed main()
{
ll x,y,l,ans=0;
cin>>x>>y;
l=x*y;//l為剩余面積
if(x>y) swap(x,y);//始終保持小的是x
while(l!=0)
{
l-=x*x;//畫(huà)一個(gè)盡可能大的正方形
y-=x;
ans+=x*4;
if(x>y) swap(x,y);
}
cout<<ans<<endl;
}優(yōu)化：不一定一個(gè)一個(gè)地劃分，可以一起劃分。?文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-829094.html
AC Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
signed main()
{
ll x,y,ans=0;
cin>>x>>y;
if(x>y) swap(x,y);
while(x!=0&&y!=0)
{
ans+=x*4*(y/x);
y%=x;
swap(x,y);
}
cout<<ans<<endl;
}結(jié)尾
本節(jié)課我們精講了三道題，記得去洛谷完成哦！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-829094.html
到了這里，關(guān)于秒懂百科，C++如此簡(jiǎn)單丨第二十天：貪心算法2的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
