题解：UVA11723 Numbering Roads

UVA 11723

题目大意

你要给 $R$ 条道路编号，编号规则为：

• 每条道路编号以一个 $1, 2, 3, \dots , N$ 之中的整数开头；

• 如果整数不够用，则在编号末尾添加一个 $\texttt{A}$ 至 $\texttt{Z}$ 之间的字母。

现在给定 $R$ 和 $N$，询问能否给每条道路分配一个独一无二的编号。如果可以，计算最少需要几个不同的字母后缀。

解题思路

因为字母后缀是可选项，最优策略应当先考虑不加字母的情况。因此可以通过一种贪心的思路，计算出最少需要的字母种类数 $X$：

$$X=\left \lfloor \dfrac{R}{N} \right \rfloor + k - 1$$

其中 $k=0$，当且仅当 $R$ 是 $N$ 的倍数；否则 $k=1$。

至此，我们只需要检查 $X$ 是否超过了 $26$，因为最多只有 $26$ 个英文字母。

参考代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<stack>
#include<queue>
#include<algorithm>
#include<cmath>
#include<vector>
//#include<unordered_map>
//#define map unordered_map
using namespace std;
/*================*/

inline int read() {
	char c=getchar();int x=0,f=1;
	for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())x=x*10+c-48;
	return x*f;
}

#define r(a) (a)=read()

int r,n,T,num;

signed main() {
	while (scanf("%d%d",&r,&n),(r||n)) {
		num=r/n+(r%n!=0)-1;
		printf("Case %d: ",++T);
		if (num>26) printf("impossible\n");
		else printf("%d\n",num);
	}
	return 0;
}