1408121428-hd-Saving HDU.cpp
3386 ワード
Saving HDU
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5292 Accepted Submission(s): 2419
Problem Description
ところで、前回は海東グループが内外の困難に直面し、会社の元老もXHD夫婦二人しか残っていないと話しました.明らかに、長年奮闘してきた商人として、XHDは死を待つことはない. ある日、彼が困っている時、突然自分の伝家の宝を思い出した.それは会社が設立された時、父がお祝いの贈り物として送ってくれた錦の袋だ.徐父はその時、やむを得ない時、開けないでくださいと言った.「今が一番必要な時ではないか」と思いながら、XHDはこの丹念に保管されている錦嚢を見つけて開けてみると、「杭城北麓千人洞に宝がある」という言葉しかなかった. 一言も言わないで、XHDは1つの大きいポケットを取って出発して、この千人洞は彼が知っているので、小さい时、お父さんはかつて彼をこの隠れた交差点に連れてきて、そして彼に教えて、これは千人洞です.彼は今やっと父の当初の言葉の意味を知った. 少し印象的でしたが、XHDはこの異常な隠れた穴を見つけるのに大きな精力を費やして、入ってみると、ほとんど呆然としていて、本当に目まぐるしいです!しかし、宝物の種類は少なくありませんが、それぞれの宝物の量は多くありません.もちろん、それぞれの宝物の単位体積の価格も違います.HDUを救うために、今すぐXHDがどれだけの価値を持つ宝物を持ち帰ることができるかを計算してください.(宝物が分割できると仮定し、分割された価値と対応する体積に比例する)
Input
入力は複数の試験例を含み、各例の第1行は2つの整数vとn(v,n<100)であり、それぞれポケットの容量と宝物の種類を表し、次いでn行は1行あたり2つの整数piとmi(0
Output
各テストインスタンスについて、XHDがどれだけの価値を取り戻すことができるかを出力してください.各インスタンスの出力は1行を占めています.
Sample Input
Sample Output
エラーの原因
タイトルのpi、miはそれぞれ単価とボリュームで、以前似たような問題をしたことがあるのでそのまま記憶に従ってプログラムを書いたが、細かい変化に気づかず、総価値を計算する際に単価しか加算されず、ボリュームに乗じず、意味が理解できず慌てて手を出した.
問題を解く構想.
欲張りアルゴリズムの水題で、まず単価を降順に並べ、単価が最大のものから選びます.もしリュックサックの体積が財宝の体積より大きいならば、総価値は単価*財宝の体積をプラスして、もし小さいならば、どのように総価値は単価*リュックサックの体積をプラスします.
コード#コード#
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 5292 Accepted Submission(s): 2419
Problem Description
ところで、前回は海東グループが内外の困難に直面し、会社の元老もXHD夫婦二人しか残っていないと話しました.明らかに、長年奮闘してきた商人として、XHDは死を待つことはない. ある日、彼が困っている時、突然自分の伝家の宝を思い出した.それは会社が設立された時、父がお祝いの贈り物として送ってくれた錦の袋だ.徐父はその時、やむを得ない時、開けないでくださいと言った.「今が一番必要な時ではないか」と思いながら、XHDはこの丹念に保管されている錦嚢を見つけて開けてみると、「杭城北麓千人洞に宝がある」という言葉しかなかった. 一言も言わないで、XHDは1つの大きいポケットを取って出発して、この千人洞は彼が知っているので、小さい时、お父さんはかつて彼をこの隠れた交差点に連れてきて、そして彼に教えて、これは千人洞です.彼は今やっと父の当初の言葉の意味を知った. 少し印象的でしたが、XHDはこの異常な隠れた穴を見つけるのに大きな精力を費やして、入ってみると、ほとんど呆然としていて、本当に目まぐるしいです!しかし、宝物の種類は少なくありませんが、それぞれの宝物の量は多くありません.もちろん、それぞれの宝物の単位体積の価格も違います.HDUを救うために、今すぐXHDがどれだけの価値を持つ宝物を持ち帰ることができるかを計算してください.(宝物が分割できると仮定し、分割された価値と対応する体積に比例する)
Input
入力は複数の試験例を含み、各例の第1行は2つの整数vとn(v,n<100)であり、それぞれポケットの容量と宝物の種類を表し、次いでn行は1行あたり2つの整数piとmi(0
Output
各テストインスタンスについて、XHDがどれだけの価値を取り戻すことができるかを出力してください.各インスタンスの出力は1行を占めています.
Sample Input
2 2 3 1 2 3 0
Sample Output
5 ，HDU ？ ， ——
エラーの原因
タイトルのpi、miはそれぞれ単価とボリュームで、以前似たような問題をしたことがあるのでそのまま記憶に従ってプログラムを書いたが、細かい変化に気づかず、総価値を計算する際に単価しか加算されず、ボリュームに乗じず、意味が理解できず慌てて手を出した.
問題を解く構想.
欲張りアルゴリズムの水題で、まず単価を降順に並べ、単価が最大のものから選びます.もしリュックサックの体積が財宝の体積より大きいならば、総価値は単価*財宝の体積をプラスして、もし小さいならば、どのように総価値は単価*リュックサックの体積をプラスします.
コード#コード#
#include<stdio.h>
#include<algorithm>
using namespace std;
struct valuable
{
int pi,mi;
}valuables[110];
bool cmp(valuable a,valuable b)
{
return a.pi>b.pi;
}
int main()
{
int n,m;
int i;
int sum;
while(scanf("%d",&n),n)
{
scanf("%d",&m);
for(i=0;i<m;i++)
scanf("%d%d",&valuables[i].pi,&valuables[i].mi);
sort(valuables,valuables+m,cmp);
sum=0;
for(i=0;i<m;i++)
{
if(n==0)
break;
else
{
if(n>=valuables[i].mi)
{
sum+=valuables[i].pi*valuables[i].mi;
n-=valuables[i].mi;
}
else
{
sum+=n*valuables[i].pi;
n=0;
}
}
}
printf("%d
",sum);
}
return 0;
}