例44 分糖果
問題描述
十個小孩圍坐一圈分糖果，開始時，老師隨機分給每位小孩若干糖果，為了公平，現進行調整，調整規則：所有小孩同時把自己糖果的一半分給左邊的小孩，調整分一半時如果哪位小孩的糖果數為一個奇數，向老師補要1塊（設老師手中的糖果足以滿足這些要求），問經過多少次調整，大家的糖果數都一樣？每人多少塊？
輸入格式
10個正整數，表示10個小孩初始糖果數，
輸出格式
調整次數和每個小孩的糖果數，
輸入樣例
15 23 18 6 14 22 9 13 8 10
輸出樣例
After 15 times,all children have same number of sugar.
Every child has 20 sugars.
（1）編程思路，
這是一道典型的模擬題，我們用逐步求精的方法來分析這個問題的解決方法，
1）先寫出程式的總體框架如下：
輸入10個小孩的初始糖果數①；
While（10個小孩的糖果數不全相等② ）
{
要進行一次調整程序，調整次數加1；
糖的塊數為奇數的小孩向老師補要一塊③ ；
所有小孩同時把自己糖果的一半分給左邊的小孩④ ；
}
輸出結果資訊
在這個總體框架中需要解決的4個問題我們用下劃線標記出來了，
2）設定義一個整型陣列a來保存10個小孩的糖果數，問題①就是需要輸入10個陣列元素的初始值，程式代碼為：
for (i=0;i<10;i++)
cin>>a[i];
3）問題②需要判斷10個小孩的糖果數是否相等，顯然是一個操作序列，其判斷結果是while回圈的條件，因此將問題②抽象成一個函式AllEqual，該函式用來判斷陣列中所有元素的值是否都相等，如果都相等則回傳1，否則回傳0，其函式原型為：
int AllEqual(int x[]);
而為判斷一個陣列中所有元素的值是否全相等，最簡單的辦法為將陣列中的第2個數至最后一個數與第1個數相比較，只要它們中有一個不相等，就回傳0（不全相等），如果比較完后，沒有回傳0，則它們全相等，回傳1，
程式描述為：
int AllEqual(int x[10])
{
int i;
for (i=1;i<10;i++)
if (x[i]!=x[0]) return 0;
return 1;
}
4）問題③可以用一個回圈程式解決，對陣列中的每個元素判斷其奇偶性，如果為奇數，則將該元素值加1，程式代碼為：
for (i=0;i<10;i++)
if (a[i]%2!=0) a[i]++;
我們將這個回圈操作寫成一個函式，函式定義如下：
void supply(int x[10])
{
int i;
for (i=0;i<10;i++)
if (x[i]%2!=0) x[i]++;
}
主函式中的呼叫陳述句為：
supply(a);
5）完成一次調整程序，所有小孩需要同時把自己糖果的一半分給左邊的小孩，如下圖1所示，
圖1 一次調整程序示例圖
由圖看出，
當i=1~9時，有 a(i)= (a(i)+a(i-1))/2
i=0時， a(0)=(a(0)+a(9))/2
因此，很容易地想到可以寫成如下的代碼段：
a[0]=a[0]/2+a[9]/2;
for (i=1;i<9;i++)
a[i]=a[i]/2+a[i-1]/2;
這樣寫是錯誤的，為什么呢？因為先修改a[1]，當計算a[2]時，用到的a[1]已經被修改了，
應該寫成：
temp=a[9];
for (i=9;i>0;i--)
a[i]=a[i]/2+a[i-1]/2;
a[0]=a[0]/2+temp/2;
問題④我們同樣將它寫成一個函式，函式定義為：
void exchange(int x[10])
{
int temp,i;
temp=x[9];
for (i=9;i>0;i--)
x[i]=x[i]/2+x[i-1]/2;
x[0]=x[0]/2+temp/2;
}
至此，可以寫出完整的源程式，
（2）源程式，
#include <stdio.h>
int AllEqual(int x[]);
void exchange(int x[]);
void supply(int x[]);
int main()
{
int a[10],i,count=0;
for (i=0;i<10;i++)
scanf("%d",&a[i]);
while (AllEqual(a)!=1)
{
count++;
supply(a);
exchange(a);
}
printf("After %d times,all children have same number of sugar.\n",count);
printf("Every child has %d sugars.\n",a[0]);
return 0;
}
int AllEqual(int x[10])
{
int i;
for (i=1;i<10;i++)
if (x[i]!=x[0]) return 0;
return 1;
}
void exchange(int x[10])
{
int temp,i;
temp=x[9];
for (i=9;i>0;i--)
x[i]=x[i]/2+x[i-1]/2;
x[0]=x[0]/2+temp/2;
}
void supply(int x[10])
{
int i;
for (i=0;i<10;i++)
if (x[i]%2!=0) x[i]++;
}
習題44
44-1 小A的糖果
本題選自洛谷題庫 （https://www.luogu.org/problem/P3817）
題目描述
小A有N個糖果盒，第i個盒中有a[i]顆糖果，
小A每次可以從其中一盒糖果中吃掉一顆，他想知道，要讓任意兩個相鄰的盒子中加起來都只有x顆或以下的糖果，至少得吃掉幾顆糖，
輸入格式
輸入包括多組測驗用例，每組用例包括兩行輸入資料，
第一行輸入N和x，
第二行N個整數，為a[i]，
輸出格式
每組測驗用例輸出一行，該行為至少要吃掉的糖果數量，
輸入樣例
3 3
2 2 2
6 1
1 6 1 2 0 4
5 9
3 1 4 1 5
輸出樣例
1
11
0
（1）編程思路，
要讓任意兩個相鄰的盒子中加起來都只有x顆或以下的糖果，可以把這幾個糖果盒成對來討論，先從第1個和第2個糖果盒開始；如果第1個糖果盒的數量就超過x了，當然至少要把它吃到剩下x個；然后如果相鄰兩個盒子中每個盒子糖果數都沒有超過x，但加起來超過x了，怎么處理呢？ 首先第1個糖果盒是只有一個分組的（和第2個）， 而第2個糖果盒卻有兩個分組（和第1個或和第3個）； 所以如果吃掉第一個糖果盒里的，只會減少一個分組的量，而如果吃掉第2個糖果盒里的，可以減少2個分組的量，所以要盡量吃掉第2個盒里的糖果，處理好第1個分組（即第1個和第2個糖果盒的分組）后，來看第2個分組（即第2個和第3個糖果盒的分組），因為第1個分組已經被處理好了，所以以后可以不管它，然后問題又變成了前一個問題，以此類推就可以求得結果，
（2）源程式，
#include <stdio.h>
int main()
{
int n,x;
scanf("%d%d",&n,&x);
int a[200001];
int i;
for (i=0;i<n;i++)
scanf("%d",&a[i]);
long long ans=0;
if (a[0]>x)
{
ans+=1ll*(a[0]-x);
a[0]=x;
}
for (i=1;i<n;i++)
{
if (a[i-1]+a[i]>x)
{
ans+=1ll*(a[i-1]+a[i]-x);
a[i]=x-a[i-1];
}
}
printf("%lld\n",ans);
return 0;
}
44-2 均分糖果
題目描述
有N個小朋友做成一排，編號分別為 1,2,…,N，每個小朋友有 ai個糖果，糖果總數為N的倍數，為了公平，現在需要進行調整，使得每位小朋友的糖果數均相等，調整方法是：編號為1的小朋友只能將糖果傳遞給編號為2的小朋友；在編號為N的小朋友，只能把糖果傳遞給編號為N-1的小朋友；其他小朋友手上的糖果，可以傳遞到相鄰左邊或右邊的小朋友手上，
現在要求找出一種調整方法，用最少的傳遞次數使每位小朋友手上的糖果數都一樣，
例如，N=4，4個小朋友手里的糖果數分別為：9 8 17 6，傳遞3次可達到目的：
3號小朋友將手里的糖果給4顆給4號小朋友（9，8，13，10），3號小朋友再將手里的糖果給3顆給2號小朋友（9，11，10，10），2號小朋友將手里的糖果給1顆給1號小朋友（10，10，10，100），每個小朋友手里均有10顆糖果，
輸入
兩行
第一行為：N（N個小朋友， 1≤N≤100）
第二行為：A1,A2, … ,An（每位小朋友手里的糖果數，1≤Ai ≤10000）
輸出
一行：即所有小朋友手里糖果數均相等時的最少傳遞次數，
輸入樣例
4
9 8 17 6
輸出樣例
3
（1）編程思路，
設n個小朋友的平均糖果數為aver，
第1位小朋友手里的糖果數與平均數的差值（a[1]-aver）只能與第2個小朋友傳遞，若多余平均值（即a[1]-aver>0），則將多余的糖果（a[1]-aver）傳遞給第2個小朋友；若小于平均值（即a[1]-aver<0），則需要第2個小朋友傳遞aver-a[1]顆糖果給他，傳遞后，第2位小朋友的糖果數為 a[2]+a[1]-aver，傳遞次數均加1，若a[1]正好等于aver，則不用傳遞，傳遞次數不變，
第一個小朋友手里的糖果數達到平均值后，可以不用管第1個小朋友了，因為他已經達到目標，再參與傳遞只會造成浪費，這樣，第2個小朋友相當是第1個小朋友了，如此類推，直到剩下最后一個小朋友，
在處理程序中，某個小朋友手里的糖果數變成負數也沒關系，其后的小朋友一定會補給他的，例如，有3個小朋友，手里的糖果數分別為：1 1 7，從左到右處理程序如下：
（1，1，7）→（3，-1，7）→（3，3，3），具體的傳遞程序可以為：3號小朋友將手里的糖果給4顆給2號小朋友（1，5，3），2號小朋友再將手里的糖果給2顆給1號小朋友（3，3，3），每個小朋友手里均有3顆糖果，由于題目只需求出最少的傳遞次數，并不要求給出具體的傳遞程序，所以從左到右處理，即使中間狀態出現負數，不會對結果造成影響，
（2）源程式，
#include <stdio.h>
int main()
{
int n;
scanf("%d",&n);
int a[105];
int i,sum=0;
for (i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
}
int aver=sum/n;
int ans=0;
for (i=1;i<=n;i++)
if ((a[i]-aver)!=0)
{
a[i+1]+=a[i]-aver;
ans++;
}
printf("%d",ans);
return 0;
}
44-3 糖果傳遞
題目描述
有n個小朋友坐成一圈，每人有ai個糖果，每人只能給左右兩人傳遞糖果，每人每次傳遞一個糖果代價為1，
輸入
小朋友個數 n，下面n行ai，
輸出
求使所有人獲得均等糖果的最小代價，
輸入樣例
4
1
2
5
4
輸出樣例
4
（1）編程思路，
設編號為i的小朋友初始有a[i]顆糖，每個小朋友的糖果數量相同，即為平均數ave，
X[i]表示第i個小朋友給第i-1個小朋友x[i]顆糖，若x[i]<0，表示第i-1個小朋友給了第i個小朋友x[i]顆糖，特別的，x[1]表示1號小朋友給n號小朋友x[1]顆糖，
因此，最后的答案就是ans=|x[1]| + |x[2]| + |x[3]| + …+ |x[n]|，
對于第1個小朋友，他給了第n個小朋友x[1]顆糖，還剩a[1]-x[1]顆糖；但因為第2個小朋友給了他x[2]顆糖，所以最后還剩a[1]-x[1]+x[2]顆糖，根據題意，最后的糖果數量等于ave，由此可得：a[1]-x[1]+x[2]=ave，
同理，對于第2個小朋友，有a[2]-x[2]+x[3]=ave
……
對于第n個小朋友，有a[n]-x[n]+x[1]=ave，
最終，可以得到n個方程，一共有n個變數，但是因為從前n-1個方程可以推匯出最后一個方程，所以實際上只有n-1個方程是有用的，
可以用x[1]表示出其他的x[i]，
對于第1個小朋友，a[1]-x[1]+x[2]=ave -> x[2]=ave-a[1]+x[1]= x[1]-S[1] （設s[1]=a[1]-ave，下面類似）
對于第2個小朋友，a[2]-x[2]+x[3]=ave ->x[3]=ave-a[2]+x[2]=2ave-a[1]-a[2]+x[1]=x[1]-s[2]
（s[2]=a[1]+a[2]-2ave=s[1]+a[2]-ave）
對于第3個小朋友，a[3]-x[3]+x[4]=ave -> x[4]=ave-a[3]+x[3]=3ave-a[1]-a[2]-a[3]+x[1]
=x[1]-s[3] （s[3]=a[1]+a[2]+a[3]-3ave=s[2]+a[3]-ave）
……
要是ans的值盡可能小，就要x[i]的絕對值之和盡量小，即
|x[1]| + |x[1]-s[1]| + |x[1]-s[2]| + …+ |x[1]-s[n-1]|要盡量小，
|x[1]-s[i]|的幾何意義是數軸上的點X[1]到s[i]的距離，所以問題變成了：給定數軸上的n個點，找出一個到它們的距離之和盡量小的點，而這個點就是這些數中的中位數，即x[1]取中位數即可，
（2）源程式，
#include <stdio.h>
#include <algorithm>
using namespace std;
long long a[1000001],s[1000001];
int main()
{
int n;
scanf("%d",&n);
int i;
long long sum=0;
for (i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
sum+=a[i];
}
long long aver=sum/n;
s[1] = a[1]-aver;
for (i=2;i<=n;i++)
s[i] = a[i]+s[i-1]-aver;
sort(s+1,s+n+1);
long long ans=0;
for (i=1;i<=n/2;i++)
ans+= s[n+1-i]-s[i];
printf("%lld",ans);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/412837.html
標籤：C
上一篇：組態檔動態重繪