Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

可能比较好理解的贪心···

Posted by 947186602 at 2020-09-19 19:59:24 on Problem 2709 and last updated at 2020-09-19 20:00:53
/**
有N种颜料的工具包,每种颜料50ml
现在给出N种颜料需要量和灰色需要量,灰色可以由任意三种颜料混合得到,问你最少需要多少颜料?

首先记录所有颜色需求里最大的,那么最大的 / 50 为至少需要
看灰色,看所有剩下颜料里是否能够混合多少灰色,实际上,混合多少灰色,为了确保利用的够好,
每次从最大的三种颜色里取(第三大变为第四大的量+1),在从变化后新的找最大的三个重复过程
**/
#include<cstdio>
#include<algorithm>
#include<string.h>
using namespace std;
int num[15],N;

int main(){
     while(~scanf("%d",&N) && N != 0){
          int max_i = 0;
          for(int i = 0;i < N;++i){
               scanf("%d",num+i);
               max_i = max_i > num[i] ? max_i : num[i];
          }
          scanf("%d",num+N);
          int res = (max_i + 49) / 50;
          for(int i = 0;i < N;++i){
               num[i] = res * 50 - num[i];
          }
          while(num[N] > 0){
               sort(num,num+N);
               if(num[N-3] == 0){
                    for(int i = 0;i < N;++i)
                         num[i] += 50;
                    res++;
               }
               if(N > 3 && num[N-4] != 0){  //每次从最大的三种颜色里取 第三大变为第四大的量+1(避免第3第4大相等,dead loop)
                   //printf("before: %d %d %d %d\n",num[N-4],num[N-3],num[N-2],num[N-1]);
                   num[N-1] -= num[N-3] - num[N-4] + 1;
                   num[N-2] -= num[N-3] - num[N-4] + 1;
                   num[N] -= num[N-3] - num[N-4] + 1;
                   num[N-3] = num[N-4] - 1;
                   //printf("after: %d %d %d %d\n",num[N-4],num[N-3],num[N-2],num[N-1]);

               }else{
                   num[N-1] -= num[N-3];
                   num[N-2] -= num[N-3];
                   num[N] -= num[N-3];
                   num[N-3] = 0;
               }
          }
          printf("%d\n",res);
     }
     return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator