CF349B - Color the Fence(贪心)

传送门:Problem - 349B - Codeforces

优先考虑位数最多,在位数最大的情况下考虑尽量使位数较高的数字更大。

取ai最小值minn,则易知最大的位数为cnt=v/minn,令全部填最小值i时的总和sum=cnt*minn

接下来按位循环,从9到1分别尝试填入,填入时判断sum+(a[i]-minn)是否大于v,不大于的话可以填入,sum+=(a[i]-minn),位数全部填完为止

 

 

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

struct U{
    int w;
    int v;
}a[10];

int b[1000010];
int n,k;
int minn=0x3f3f3f3f;
int flag=0;
int main(){
    cin>>n;
    for(int i=1;i<=9;i++)
    {
        cin>>a[i].w;
        a[i].v=i;
        if(a[i].w<minn)
        {
            minn=a[i].w;
            flag=i;
        }
    }
    int cnt=n/a[flag].w;
    int sum=cnt*a[flag].w;
    if(cnt==0)
    {
        cout<<-1;
        return 0;
    }
    for(int i=9;i>=1;i--)
    {
        int t=a[i].w-a[flag].w; 
        while(sum+t<=n&&k!=cnt)
        {
            k++;
            b[k]=i;
            sum+=t;
        }
    }
    for(int i=1;i<=cnt;i++)cout<<b[i];
    return 0;
}

 

上一篇:fencing— Red hat cluster


下一篇:MFS分布式文件的高可用