首页 > ACM题库 > HDU-杭电 > hdu 2194 Help the vendor and get some M ^_^-贪心[解题报告]C++
2013
12-30

hdu 2194 Help the vendor and get some M ^_^-贪心[解题报告]C++

Help the vendor and get some M ^_^

问题描述 :

A doll vendor has just received a shipment of dolls from the factory. The vendor can only sell dolls in pairs, and have to ensure that in each pair one doll is K times as large as the other. What is the maximum number of pairs that the vendor can assemble? Each doll can only be sold one time. Now the vendor wants your help to solve this problem. Of course, he will give you 30% of the profit, so, what are you waiting for?

输入:

There are multiple test cases.For each case the input contains two integers N (1<=50<=N) and K (1<=K<=25) in first line and N doll sizes (integers between 1 and 100000, inclusive) below, where N is the number of dolls. The doll sizes may separated by white spaces or newline.Input ends when N and K is 0.

输出:

There are multiple test cases.For each case the input contains two integers N (1<=50<=N) and K (1<=K<=25) in first line and N doll sizes (integers between 1 and 100000, inclusive) below, where N is the number of dolls. The doll sizes may separated by white spaces or newline.Input ends when N and K is 0.

样例输入:

5 2
1 2 1 2 4
0 0

样例输出:

2

Hint: you can sell two pairs at most, {(1,2),(1,2)} or {(1,2),(2,4)}.


这道题也是一道比较简单的贪心题。
思路:
将所有玩具的大小按从大到小排序。从第一个数开始找大小是当前玩具大小K倍的玩具。并标记。同时,当找到一对后,马上跳出内层循环(因为这个,wa了几次)。
代码:

#include<iostream>
using namespace std;
bool vis[60];
int num[60];
bool compare(int a,int b)
{
     return a<b;
}
int main()
{
    int n,k,sum,temp;
    while(scanf("%d%d",&n,&k)!=EOF&&!(n==0&&k==0))
    {
                 sum=0;
                 memset(vis,false,sizeof(vis));
                 for(int i=0;i!=n;i++)
                 {
                         scanf("%d",&num[i]);
                         vis[i]=true;
                 }
                 sort(num,num+n,compare);
                 for(int i=0;i<n;i++)
                 {
                         if(vis[i])//当前玩具未被出售
                         {
                                   for(int j=i+1;j<n;j++)//寻找未被出售而且大小是当前玩具的k倍的玩具
                                   {
                                           if(vis[j]&&num[j]==k*num[i])
                                           {
                                                                       sum++;
                                                                       vis[i]=vis[j]=false;
                                                                       break;
                                           }
                                   }
                         }
                 }
                 cout<<sum<<endl;
    }
return 0;
}