貪心：貪心算法谒兄，又叫貪婪算法，如其名社付，貪心承疲，就是得到眼前的利益，而不關(guān)心未來(lái)（現(xiàn)實(shí)中千萬(wàn)不要這么做Ｅ缚АＱ喔搿！）啼辣，但在OI中有時(shí)有奇效哦啊研。
他的思想就是只看當(dāng)前的利益，得到答案只看當(dāng)前所要求的最大（最信概 ）值悲伶。
說(shuō)了這么多還是沒(méi)懂，做題來(lái)看看吧住涉！
P1223 排隊(duì)接水
分析一下這道題目：這道題目很明顯是貪心算法，思路就是給等待時(shí)間排序（序號(hào)跟著走）钠绍，最后把所排序的隊(duì)列輸出序號(hào)舆声，算出所有的等待時(shí)間的平均并輸出。這是入門(mén)題目柳爽，可以作為貪心基礎(chǔ)的參考
#include<bits/stdc++.h>
using namespace std;
struct qaq
{
double t;//等待時(shí)間
int cnt;//序號(hào)
}; //結(jié)構(gòu)體計(jì)數(shù)媳握，以達(dá)到一個(gè)等待時(shí)間排序，而序號(hào)則跟著走;
bool cmp(qaq x,qaq y)
{
return x.t<y.t;
}//cmp是排序數(shù)組（可改sort排序順序磷脯，最重要的是為了達(dá)到結(jié)構(gòu)體建立目的;
struct qaq a[100005];
int main()
{
double ti=0;
int n,o;
cin>>n;
o=n;//o是為了方便計(jì)算等待時(shí)間蛾找，大家可以自己想一想為什么
for(int i=1;i<=n;i++)
{
cin>>a[i].t;
a[i].cnt=i;
}//輸入
sort(a+1,a+n+1,cmp);//排序
for(int i=1;i<=n;i++)
{
o--;
ti=ti+a[i].t*o;
}//統(tǒng)計(jì)平均時(shí)間
for(int i=1;i<n;i++)
{
cout<<a[i].cnt<<" ";
}
ti=ti/n;
cout<<a[n].cnt<<endl;
cout<<fixed<<setprecision(2)<<ti;//輸出
return 0;
}
第二種：背包拿東西，算最大利益赵誓。這種題型也分兩種：一個(gè)是拿的東西可以分割打毛，第二種是不能分割的。我們今天來(lái)看簡(jiǎn)單的（可以分割的）
P2240 部分背包問(wèn)題
這道題的思路就是算出所有的物品每個(gè)重量單位的價(jià)值俩功，排序幻枉，從大到小拿取，知道裝滿或沒(méi)有東西可以放了诡蜓。廢話少說(shuō)熬甫，上代碼！
#include<bits/stdc++.h>
using namespace std;
struct qaq
{
int kg;
double mo;
double km;//多了一個(gè)蔓罚，是用于計(jì)算每個(gè)重量單位的價(jià)值
}; //結(jié)構(gòu)體椿肩，作用與上一題一致（排隊(duì)打水）
bool cmp(qaq x,qaq y)
{
return x.km<y.km;
}//效果同上一題
struct qaq a[1000005];
int main()
{
double mon=0;
int n,big,bag=0,x;
cin>>n>>big;
for(int i=1;i<=n;i++)
{
cin>>a[i].kg;
cin>>a[i].mo;
a[i].km=a[i].mo/a[i].kg;//算出每個(gè)重量單位的價(jià)值
}//輸入
sort(a+1,a+n+1,cmp);//排序
for(int i=n;i>=1;i--)
{
if(bag+a[i].kg>big)
{
x=big-bag;
mon=mon+a[i].km*x;
cout<<fixed<<setprecision(2)<<mon;
return 0;
}//如果加上重量后背包滿了瞻颂，則加上最大能拿取得金幣
else if(bag+a[i].kg==big)
{
mon=mon+a[i].mo;
cout<<fixed<<setprecision(2)<<mon;
return 0;
}//如果相等，則加上所有金幣以后直接輸出
else
{
bag=bag+a[i].kg;
mon=mon+a[i].mo;
}//排除以上得一些情況郑象，則為加上整堆金幣不滿贡这，則直接加上
}
cout<<fixed<<setprecision(2)<<mon;//如果所有金幣都放入背包都沒(méi)有滿背包，則輸出
return 0;
}
貪心的基礎(chǔ)基礎(chǔ)想法就到這里扣唱，之后會(huì)有貪心的進(jìn)階藕坯，如哈夫曼編碼等，敬請(qǐng)期待噪沙！
課后作業(yè)：CF545D Queue
大家盡量AC啊炼彪，比較簡(jiǎn)單的！
