HDU 5884 Sort

正文索引 [隐藏]

题目翻译
题解
代码

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5884

题目翻译

有一个长度为N的序列，合并序列总代价不能超过T，每次操作最多可以合并k个，合并的代价是这k个数字的和。求把序列合并成一个元素，且总代价不超过T的最小的k。

题解

我们首先这是合并果子问题，我们每次肯定取最小的前k个合并，但是这是刚好能合并成一个的情况，如果发现最后合并时不足k个，我们可以考虑给序列一开始补上一些不影响结果的0 。然后取前k个使用优先队列+一些小优化，因为初始的数字很小，但是数量很多，所以我们给<1000的数字计数，这样小于1000的数字出队的复杂度接近O(1) 。

代码

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int Maxn=100000;
int n,lim;
int num[Maxn+5];
int cnt[1005];
struct NumberNode{
    int x;
    NumberNode(){}
    NumberNode(int x0){
        x=x0;
    }
    bool operator < (const NumberNode &a) const {
        return x>a.x;
    }
};
priority_queue<NumberNode> que;
int siz;
inline void clear(){
    while(!que.empty()) que.pop();
    memset(cnt,0,sizeof(cnt));
    siz=0;
}
inline void push(int x,int val){
    siz+=val;
    if (x<=1000){
        if (cnt[x]==0) que.push(NumberNode(x));
        cnt[x]+=val;
    }else{
        for (int i=1;i<=val;i++) que.push(NumberNode(x));
    }
}
inline int pop(){
    siz--;
    int now=que.top().x;
    if (now<=1000){
        cnt[now]--;
        if (!cnt[now]) que.pop();
    }else{
        que.pop();
    }
    return now;
}
inline bool judge(int k){
    if (k==1) return false;
    clear();
    for (int i=1;i<=n;i++)   push(num[i],1);
    int siz_zero=( (int)((n-1)/(k-1)) + ((n-1)%(k-1)!=0?1:0) )*(k-1)+1-n;
    if (siz_zero)   push(0,siz_zero);
    //printf("siz_zero=%d k=%d\n",siz_zero,k);
    int totCst=0;
    while(siz!=1){
        int merg=0;
        for (int i=1;i<=k;i++){
            int now=pop();
            merg+=now;
            //printf("Get %d\n",now);
        }
        //printf("Merge %d\n",merg);
        if (merg>lim || totCst+merg>lim) return false;
        totCst+=merg;
        push(merg,1);
    }
    if (totCst<=lim) return true;
    return false;
}
inline void solve(int T){
    scanf("%d%d",&n,&lim);
    for (int i=1;i<=n;i++) scanf("%d",&num[i]);
    int left=1,right=n,Ans=n+1;
    while(left<=right){
        int mid=(left+right)/2;
        //printf("Try Left=%d Right=%d %d",left,right,mid);
        if (judge(mid)){
            //printf(" Success!\n");
            right=mid-1;
            Ans=min(mid,Ans);
        }else{
            //printf(" Failed!\n");
            left=mid+1;
        }
    }
    printf("%d\n",Ans);
}
int main(){
    freopen("in.txt","r",stdin);
    int T=0;
    while(scanf("%d",&T)!=EOF)
        for (int i=1;i<=T;i++)
            solve(i);
    return 0;
}

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

const int Maxn=100000;

int n,lim;

int num[Maxn+5];

int cnt[1005];

struct NumberNode{

int x;

NumberNode(){}

NumberNode(int x0){

x=x0;

}

bool operator < (const NumberNode &a) const {

return x>a.x;

}

};

priority_queue<NumberNode> que;

int siz;

inline void clear(){

while(!que.empty()) que.pop();

memset(cnt,0,sizeof(cnt));

siz=0;

}

inline void push(int x,int val){

siz+=val;

if (x<=1000){

if (cnt[x]==0) que.push(NumberNode(x));

cnt[x]+=val;

}else{

for (int i=1;i<=val;i++) que.push(NumberNode(x));

}

inline int pop(){

siz--;

int now=que.top().x;

if (now<=1000){

cnt[now]--;

if (!cnt[now]) que.pop();

}else{

que.pop();

}

return now;

}

inline bool judge(int k){

if (k==1) return false;

clear();

for (int i=1;i<=n;i++) push(num[i],1);

int siz_zero=( (int)((n-1)/(k-1)) + ((n-1)%(k-1)!=0?1:0) )*(k-1)+1-n;

if (siz_zero) push(0,siz_zero);

//printf("siz_zero=%d k=%d\n",siz_zero,k);

int totCst=0;

while(siz!=1){

int merg=0;

for (int i=1;i<=k;i++){

int now=pop();

merg+=now;

//printf("Get %d\n",now);

}

//printf("Merge %d\n",merg);

if (merg>lim || totCst+merg>lim) return false;

totCst+=merg;

push(merg,1);

}

if (totCst<=lim) return true;

return false;

}

inline void solve(int T){

scanf("%d%d",&n,&lim);

for (int i=1;i<=n;i++) scanf("%d",&num[i]);

int left=1,right=n,Ans=n+1;

while(left<=right){

int mid=(left+right)/2;

//printf("Try Left=%d Right=%d %d",left,right,mid);

if (judge(mid)){

//printf(" Success!\n");

right=mid-1;

Ans=min(mid,Ans);

}else{

//printf(" Failed!\n");

left=mid+1;

}

printf("%d\n",Ans);

}

int main(){

freopen("in.txt","r",stdin);

int T=0;

while(scanf("%d",&T)!=EOF)

for (int i=1;i<=T;i++)

solve(i);

return 0;

}

一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

WNJXYKの博客

喂你脚下有坑

HDU 5884 Sort

题目翻译

题解

代码

扫一扫支付

评论放弃治疗

创作日历

文章

标签云

最近访客

HDU 5884 Sort

题目翻译

题解

代码

扫一扫支付

评论 放弃治疗

评论放弃治疗