HDOJ_2187 悼念512汶川大地震遇難同胞——老人是真餓了
1.題目
Problem Description
對于幸存的災民來說,最急待解決的顯然是溫飽問題,救災部隊一邊在組織人員全力打通交通,一邊在組織采購糧食。現在假設下撥了一定數量的救災經費要去市場采購大米(散裝)。如果市場有m種大米,各種大米的單價和重量已知,請問,為了滿足更多災民的需求,最多能采購多少重量的大米呢?
Input
輸入資料首先包含一個正整數C,表示有C組測試用例,每組測試用例的第一行是兩個整數n和m(0<n<=1000,0<m<=1000),分别表示經費的金額和大米的種類,然後是m行資料,每行包含2個整數p和h(1<=p<=25,1<=h<=100),分别表示單價和對應大米的重量。
Output
對于每組測試資料,請輸出能夠購買大米的最多重量(你可以假設經費買不光所有的大米)。
每個執行個體的輸出占一行,保留2位小數。
Sample Input
1
7 2
3 3
4 4
Sample Output
2.33
2.分析
1.顯而易見這是一道貪婪算法題,先購買單價小的大米,買完後在買次小的。
2.算法1.快排.适當改造,符合結構體特點
2.貪婪算法.若rem(剩餘的錢)-p/weight>0,則可以買完,跟新rem與sum(購買的糧食總重量)
若<=,令sum+=rem/(float)p,結束循環,以.2f格式輸出sum。
3.AC代碼
#include <bits/stdc++.h>
using namespace std;
typedef struct date
{
int p;
int weight;
}DA;
DA da[1000];
void Sort(int l, int r)
{
int p,_max,_min,wei;
if(l>=r)
return;
_max=r;_min=l;
p=da[l].p;
wei=da[l].weight;
while(_min<_max)
{
if(p==da[_max].p)
_max--;
while(_min<_max&&da[_max].p>p)
{
_max--;
}
if(_min<_max)
{
da[_min].p=da[_max].p;
da[_min].weight=da[_max].weight;
}
while(_min<_max&&da[_min].p<p)
{
_min++;
}
if(_min<_max)
{
da[_max].p=da[_min].p;
da[_max].weight=da[_min].weight;
}
if(_min>=_max)
{
da[_max].p=p;
da[_max].weight=wei;
}
}
Sort(l,_min-1);
Sort(_max+1,r);
}
int main()
{
int c,n,m,i,rem;
float sum;
cin>>c;
while(c--)
{
cin>>n>>m;
rem=n;
sum=0;
for(i=0;i<m;i++)
{
cin>>da[i].p>>da[i].weight;
}
Sort(0,m-1);
for(i=0;i<m;i++)
{
if(rem-da[i].p*da[i].weight>0)
{
rem=rem-da[i].p*da[i].weight;
sum+=da[i].weight;
}
else
{
sum+=(float)rem/(float)da[i].p;
break;
}
}
printf("%.2f\n",sum);
}
return 0;
}