Codeforces 226B Naughty Stone Piles 貪心 – JAVA編程語言程序開發技術文章

題意:有n(1<=n<=10^5)堆石子,每堆有ai(1<=ai<=10^9)個石子,每次將一堆石子a合並到另一堆b花費為a,求把所有石子合並一起的最小花費。
         不過沒有那麼簡單,現在有m(1<=m<=10^5)個詢問ki(1<=ki<=10^5),問每堆石子至多被合並ki次,求把所有石子合並在一起的最小花費。
題解:看到數據量顯然貪心+亂搞。
         首先想ki = 1的情形,不難想到,一堆石子被合並一次,一堆石子被合並一次…一堆石子被合並一次,這顯然是讓最少的石子去合並別的石子n-1次。
         考慮ki = 2,一堆石子被合並二次,二堆石子被合並二次,四堆石子被合並二次…即每次*2。
         很好理解,每次可以合並的堆的個數增加瞭,被合並的堆數也在增加。所以排序後,從大到小貪心即可。
         卡在__int64上居然是re,唉還是考慮不周全10^5不會超int,但是10^5 * 10^5就果斷超瞭唉,比賽可惜瞭…
PS:cf紫瞭,下場估計要掉rt瞭…

Sure原創,轉載請註明出處。
[cpp] 
#include <iostream> 
#include <cstdio> 
#include <memory.h> 
#include <algorithm> 
using namespace std; 
const int maxn = 100002; 
__int64 stone[maxn],sum[maxn],ans[maxn]; 
int m,n,q; 
 
bool cmp(__int64 a,__int64 b) 

    return a > b; 

 
void read() 

    memset(ans,-1,sizeof(ans)); 
    for(int i=0;i<n;i++) 
    { 
        scanf("%I64d",&stone[i]); 
    } 
    sort(stone , stone + n , cmp); 
    sum[0] = 0LL; 
    sum[1] = stone[1]; 
    for(int i=2;i<n;i++) 
    { 
        sum[i] = sum[i-1] + stone[i]; 
    } 
    return; 

 
void solve() 

    scanf("%d",&m); 
    bool flag = false; 
    while(m–) 
    { 
        if(flag) printf(" "); 
        scanf("%d",&q); 
        if(ans[q] != -1) 
        { 
            printf("%I64d",ans[q]); 
            continue; 
        } 
        __int64 res = 0; 
        __int64 cnt = q,val = 1; 
        for(__int64 i=1;i<1LL * n;) 
        { 
            int top; 
            if(cnt+i-1 > 1LL * (n-1)) top = n-1; 
            else top = (int)(cnt+i-1); 
            res += (sum[top] – sum[i-1]) * val; 
            i += cnt; 
            val++; 
            cnt *= 1LL * q; 
        } 
        ans[q] = res; 
        printf("%I64d",res); 
        flag = true; 
    } 
    puts(""); 
    return; 

 
int main() 

    while(~scanf("%d",&n)) 
    { 
        read(); 
        solve(); 
    } 
    return 0; 

發佈留言