程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA 10560 - Minimum Weight(數論)

UVA 10560 - Minimum Weight(數論)

編輯:C++入門知識

UVA 10560 - Minimum Weight

題目鏈接

題意:有一個天枰,給定n,要求出能稱出1 - n重量所需最少的砝碼,然後給k個數字,分別表示出怎麼去稱這k個數字。

思路:首先先求出最少砝碼,1肯定是需要的,然後1可以組成1,然後要1個3,就可以組成2,3,4觀察後發現,其實每次添加砝碼,就添加當前砝碼總質量和 * 2 + 1.

證明:當前砝碼能組成[1, sum]那麼在多一個砝碼,如果有2 sum + 1, 那麼[sum + 1, 2 sum + 1]的情況都可以組成,這樣是最優的使得砝碼最少。

然後剩下就是去表示重量如何組成了,其實就是加加減減,判斷當前重量是否在sum[i - 1] 和 sum[i]之間,如果是的話,就是可以用一個need[i]這個砝碼,至於加減,就要看之前的情況了,我是用了一個flag來標記。

代碼:

#include 
#include 

const int N = 105;
const char fh[5] = "+-";
unsigned long long n, need[N], sum[N], w;
int k, nn = 0;

void solve(int i, unsigned long long w) {
    int flag = 1;
    while (w) {
	for (;i >= 1; i--) {
	    if (w <= sum[i] && w > sum[i - 1]) {
		printf("%llu", need[i]);
		if (w > need[i]) {
		    w -= need[i];
		    printf("%c", fh[(!flag)]);
		}
		else if (w < need[i]) {
		    w = need[i] - w;
		    printf("%c", fh[flag]);
		    flag = (!flag);
		}
		else w = 0;
		i--;
		break;
	    }
	}
    }
    printf("\n");
}

int main() {
    unsigned long long Max = (1ULL<<63), now = 0;
    while (now < Max) {
	nn++;
	now = sum[nn - 1] * 2 + 1;
	sum[nn] = sum[nn - 1] + now;
	need[nn] = now;
    }
    need[++nn] = (1ULL<<64) - 1;
    sum[nn] = need[nn];
    while (~scanf("%llu%d", &n, &k) && n || k) {
	int i = 1;
	for (; i <= nn; i++) {
	    if (n <= sum[i]) break;
	}
	printf("%d", i);
	for (int j = 1; j <= i; j++)
	    printf(" %llu", need[j]);
	printf("\n");
	while (k--) {
	    scanf("%llu", &w);
	    solve(i, w);
	}
    }
    return 0;    
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved