Beyond the Void
BYVoid
POI 1998 最輕的語言 The lightest language
本文正體字版由OpenCC轉換

從描述中看出,非前綴且權值和最小,於是我想到了哈夫曼編碼。類似的,對於這道題,我們可以考慮建立一個k叉樹,這個樹的每個葉節點代表一個字符串,只須找出最小的n個葉節點的權值,就是結果。

首先建立一個0節點,在此基礎上首先加入每個單個字母,當葉節點的個數不足n個時,取出最小的一個節點,對這個節點進行擴展,即把它的權值分別加上每個字母的權值,作爲新的k個葉節點。否則把前n小的節點取出,計算它們的權值之和。如果這個和小於當前已知最優解,更新最優解,否則結束,因爲再擴展一定不會比當前值小。

實際上我們並不需要建立樹結構,只需要對葉節點的權值抽象的維護。首先把每個字母的權值插入優先隊列,每次取出前n小的值計算,並以最小值來維護。

一般情況下我們用最小堆實現優先隊列,但是堆中可能會存在n^2個元素,大大超過了空間限制。但是優先隊列中只有前n小的元素是對我們有用的,我們可以以此改進堆,只存儲前n小的元素。當插入一個新的元素時,把堆中的最大值刪除,這樣維護的一定是前n小的。這樣又會帶來新的問題,在最小堆中取最大值是O(n)時間複雜度的。於是必須同時維護一個最大堆,使取刪最大值變爲O(logn)。需要同時維護兩個堆,在每個元素之間建立映射關係,每次刪除都要對兩個堆進行維護。

這樣雖然可以解決問題,但是會大大增加編程的複雜度,可以考慮不用堆來維護。我用了更強大的數據結構,平衡樹。平衡樹在插入、取最大、取最小、刪除上均有O(logn)的時間複雜度,使用平衡樹可以使編程思路更清晰。我用的是Treap。

以下是我用Treap實現的代碼。

/* 
 * Problem: POI1998 naj
 * Author: Guo Jiabao
 * Time: 2008.12.3 20:03:22
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

class tTreap
{
	public:
		class tNode
		{
			public:
				int v,fix;
				tNode *l,*r;
				tNode(int tv,tNode *nl): v(tv),l(nl),r(nl)
				{
					fix=rand();
				}
		};
		tNode *root,*null;
		int sum,size,lim;
		tTreap()
		{
			root=null=new tNode(0,0);
			sum=0;
		}
		void rot_r(tNode *&p)
		{
			tNode *q=p->l;
			p->l=q->r;
			q->r=p;
			p=q;
		}
		void rot_l(tNode *&p)
		{
			tNode *q=p->r;
			p->r=q->l;
			q->l=p;
			p=q;
		}
		void _ins(tNode *&p,int v)
		{
			if (p==null)
			{
				p=new tNode(v,null);
			}
			else if (v <= p->v)
			{
				_ins(p->l,v);
				if (p->l->fix < p->fix)
					rot_r(p);
			}
			else
			{
				_ins(p->r,v);
				if (p->r->fix < p->fix)
					rot_l(p);
			}
		}
		void ins(int v)
		{
			_ins(root,v);
			size++;
			sum+=v;
			if (size>lim)
				delmax();
		}
		int _delmin(tNode *&p)
		{
			if (p->l==null)
			{
				int v=p->v;
				tNode *t=p;
				p=p->r;
				delete t;
				return v;
			}
			else
			{
				return _delmin(p->l);
			}
		}
		int _delmax(tNode *&p)
		{
			if (p->r==null)
			{
				int v=p->v;
				tNode *t=p;
				p=p->l;
				delete t;
				return v;
			}
			else
			{
				return _delmax(p->r);
			}
		}
		int delmin()
		{
			size--;
			int r=_delmin(root);
			sum-=r;
			return r;
		}
		int delmax()
		{
			size--;
			int r=_delmax(root);
			sum-=r;
			return r;
		}
};

const int MAXK=30;
const int INF=0x7FFFFFFF;

tTreap T;
int W[MAXK];
int N,K,Ans;

void init()
{
	int i;
	freopen("naj.in","r",stdin);
	freopen("naj.out","w",stdout);
	scanf("%d%d",&N,&K);
	T.lim=N;
	for (i=1;i<=K;i++)
	{
		scanf("%d",&W[i]);
		T.ins(W[i]);
	}
	Ans=INF;
}

void solve()
{
	int i,A;
	while (T.sum<Ans)
	{
		if (T.size>=N)
		{
			if (T.sum<Ans)
				Ans=T.sum;
			else
				break;
		}
		A=T.delmin();
		for (i=1;i<=K;i++)
		{
			T.ins(A+W[i]);
			
		}
	}
}

int main()
{
	init();
	solve();
	printf("%d",Ans);
	return 0;
}
<h2><span class="mw-headline">最輕的語言</span></h2>

字母表AK由英文字母表的大寫字母K組成。一個被稱作重量的正整數被委派給字母表的每一個字母。一個由字母表AK的字母組成的字符串的重量是這個字 符串的所有字母的總重量。一個基於字母表AK的語言由這個字母表的字母組成的字符串的有限集合。一個語言的重量是所有它的字符串的重量之和。如果這個語言 的任意兩個字符串W、V,W不是V的前綴,那我們說這個語言不是前綴的。

我們想找出基於字母表AK的N個要素的非前綴語言的可能的最小重量。

例如

假設K=2,字母a的重量W(a)=2 字母b的重量W(b)=5。字符串ab的重量W(ab)=2+5=7。 W(aba)=2+5+2=9。語言J={ab,aba,b}的重量-W(J)=21。語言J不是非前綴,因爲字符串ab是aba的前綴。基於字母表A2最輕的三元非前綴語言(假設字母的重量如前)是{b,aa,ab};它的重量是16。

任務

寫一個程序:
  • 從文本文件中讀取兩個整數n,k和字母表Ak 的k個字母的重量;

  • 計算基於字母表Ak 的非前綴的n元語言的最小重量;

  • 把結果寫到文本文件。

    輸入

    在輸入文件的首行有兩個被空格號分開的正整數n、k(2<=n<=10000, 2<=k<=26)。它們是語言中的字符串數和字母表中各個字母數。第二行包括被空格號隔開的k個正整數。每一個都不大於10000。第I個數是第I個字母的重量。

    輸出

    在輸出文件的首行應該寫一個整數-基於字母表Ak 的最輕的非前綴的n元語言重量。

    樣例輸入

    3 2
      2 5

    樣例輸出

    16

上次修改時間 2017-02-03

相關日誌