思路:找出最大堆的鵝卵石數為max,最小堆數為min。如果max-min>=k,則成立。
證明:對最大堆編號為:a1,a2,a3~amin-1,amin~amax .對最小堆編號為:b1,b2~bmin.
讓a1和b1,a2和b2,......,amin和bmin顏色一樣。
對於剩下的amin+1~amax 鵝卵石不能出現重復顏色,一旦出現就會是2-0>1.
所以:剩下的石頭數必須小於k. 得證。
至於其他鵝卵石數在最小和最大數之間的很容易證明可行。
至於對每一個鵝卵石的塗色,直接循環塗1~k,即可,這樣最均衡。
學習:比賽的時候要深入思考,必須要用草稿紙,在頭腦裡空想是不夠的。
我的代碼:
#include#include int main(void){ int t,k,str[100]; while(~scanf(%d%d,&t,&k)){ int min=100000,max=0; for(int i=0;i < t;i++){ scanf(%d,&str[i]); if(str[i] < min) min=str[i]; if(str[i] > max) max=str[i]; } if(max-min <= k){ printf(YES ); for(int i=0;i < t;i++){ for(int j=0,kk=0;j < str[i];j++,kk++){ if(j) printf( ); printf(%d,kk%k+1); } printf( ); } }else printf(NO ); } return 0; }