首页 > 代码库 > uva--10670Work Reduction +模拟

uva--10670Work Reduction +模拟

题意:

     现在有n份工作需要做,老板要求必须一天之内做到只剩m份;你可以选择一些机构来帮你完成工作,他们的收费标准是:收费$A完成一份工作,收费$B完成你一半的工作(如果除2后有小数,则四舍五入)。输入L个这样机构的收费,你需要算出完成你工作每个机构最低的收费,并且从低到高排序后输出(费用相同,则按机构名的字典序排序)。

思路:

   如果剩余工作完成一半后仍大于m,我们就选择完成一半的工作,然后比较一下在两种付费方式下那种费用更小,我们就采用那种。如果剩余工作完成一半以后小于m,我们就采用方式1付剩下的费用。

   按照这样的思路我们算出每个机构的最低费用然后再排序输出。注意一下strcmp()函数:strcmp(a,b),如果a,b相等则返回0,如果a>b则返回1,如果a<b,则返回-1;另外使用sscanf()函数从字符串中提取数据时,注意其分隔符必须是空格。


代码如下:


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

typedef struct
{
        char name[100];
        int cost;
}P;
P p[110];

int cmp(P p1,P p2)
{
         if(p1.cost==p2.cost)
               return strcmp(p1.name,p2.name)<0? 1 : 0 ;
        return p1.cost<p2.cost;
}


int main()
{
      int i,j,k,n,m,L,t,Case=0;
      scanf("%d",&t);
      while(t--)
      {
             scanf("%d%d%d",&n,&m,&L);
             k=0;
             for(i=0;i<L;i++)
             {
                     int n1=n;
                     char str[110],name[110];
                     int A,B;
                     scanf("%s",str);
                     int len=strlen(str);
                     for(j=0;j<len;j++)
                           if(str[j]==':'||str[j]==',')
                                  str[j]=' ';
                     ///利用sscanf提取数据时,必须保证其分隔符是空格
                     sscanf(str,"%s%d%d",&name,&A,&B);
                     int sum=0;
                     while(1)
                     {
                             int t=ceil((double)n1/2);
                             if(n1-t<m)
                             {
                                    sum+=(n1-m)*A;
                                    break;
                             }
                             else
                             {
                                    if(t*A>B)
                                       sum+=B;
                                    else
                                       sum+=t*A;
                                       n1-=t;
                             }
                     }
                     strcpy(p[k].name,name);
                     p[k].cost=sum;
                     k++;
             }
             sort(p,p+k,cmp);
             printf("Case %d\n",++Case);
             for(i=0;i<k;i++)
                 printf("%s %d\n",p[i].name,p[i].cost);
      }
   return 0;
}





uva--10670Work Reduction +模拟