codeforces #339 div2 D

Posted by 111qqz on Saturday, February 20, 2016

TOC

http://codeforces.com/contest/613/problem/B 题意:有n个技能,初始每个技能的level为a[i],每个技能最大level为A(不妨称为满级技能),设满级技能个数为maxnum,最小的技能level为minval,问如何将m个技能点分配到n个技能上使得cfmaxsum+cmminval (n<=1E5,a[i],A<=1E9,cf,cm<=1E3,m<=1E15)

思路:贪心。如果让有限的maxsum个技能满级的话,那么一定是让初始最大的maxsum技能满级更优。我们O(n)可以预处理一个c[i]数组,表示将i个技能变成最大值的最小花费。

然后再预处理一个前缀和数组,sum[i]表示初始最小的i个的技能的花费之和。

然后从0到n枚举变成最大值的技能的个数,在剩下的技能中二分能达到的最小值。

注意要按照原来顺序输出,所以记得记录id.

/* ***********************************************
Author :111qqz
Created Time :2016年02月20日 星期六 13时11分30秒
File Name :code/cf/#339/D.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E5+7;
LL n,A,cf,cm,m;
LL b[N];
LL c[N]; //c[i]表示将i个变为最大值需要的最少花费
LL sum[N] ; //sum[i]表示花费最少的i个的价值和
struct node
{
    LL val;
    int id;

    bool operator < (node b)const
    {
    return val>b.val;
    }
}a[N];

bool cmp (LL a,LL b)
{
    return a<b;
}
bool cmp2( node a,node b)
{
    return a.id<b.id;
}
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
  #endif
    ios::sync_with_stdio(false);
    cin>>n>>A>>cf>>cm>>m;
    for ( int i = 1 ; i <= n ; i++) cin>>a[i].val,a[i].id =  i,b[i] = a[i].val;
    sort(b+1,b+n+1,cmp);
    sort(a+1,a+n+1);
	
    LL cost = 0 ;
    c[0] = 0;
    for ( int i = 1 ; i <= n ; i++)
    {
        cost +=A-a[i].val;
        c[i] = cost;
    }
    sum[0] = 0LL;
    for ( int i = 1 ; i <= n ; i++) sum[i] = sum[i-1] + b[i];

    LL maxnum;
    LL minval;
    LL ans = -1;
    for ( int i = 0 ; i <= n ; i++) //i表示达到最大值的有i个
    {
        LL M = m;
        LL left = M - c[i];
        if (left<0) break;

        LL l=0,r=A;
	    
        while (l<r) //在剩下的n-i个数里二分最小值
        {
        LL mid = (l+r+1)>>1;
        int x= lower_bound(b+1,b+n-i+1,mid)-b-1;
        if (mid*x-sum[x]<=left) l = mid;
        else r = mid -1;
        }

        if (cf*i+cm*l>ans)
        {
        ans = cf*i+cm*l;
        maxnum  = i;
        minval = l;
        }
    }

    for ( int i = 1 ; i <= maxnum ; i++) a[i].val = A;
    for ( int i = 1 ; i <= n ; i++) if (a[i].val<minval) a[i].val = minval;
    sort(a+1,a+n+1,cmp2);
    cout<<ans<<endl;
    for ( int i = 1 ; i <= n-1 ; i++) cout<<a[i].val<<" ";
    cout<<a[n].val<<endl;

  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付