首页 > 试题广场 >

圈圈

[编程题]圈圈
  • 热度指数：34 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解
shy有一个队列a[1], a[2],…,a[n]。现在我们不停地把头上的元素放到尾巴上。在这过程中我们会得到n个不同的队列，每个队列都是a[k],a[k+1],…,a[n],a[1],…,a[k-1]的形式。在这些队列中，我们可以找到字典序最小的。
shy无聊的时候会给队列的每个元素加一玩。但是为了使得游戏不这么无聊，shy加一以后会给每个元素模m，这样子字典序最小的序列就会变了，生活就变得有趣。
很显然这样子加m次以后，序列会变成原来的样子。所以现在shy想知道，在他没有加一前，加一时，加二时,….,加m-1时字典序最小的序列的第k（和上面的k没有关系）个元素分别是几。

输入描述:
第一行三个整数n，m，k表示序列长度，取模的数和要求的序列的第几个元素。
接下来一行n个整数表示初始序列。


输出描述:
m个整数表示答案。
示例1

输入

5 6 3
1 2 1 2 3

输出

1
2
3
5
5
0

备注:
对于30%的数据，1≤n,m≤100；
对于100%的数据，1≤n,m≤50000, 1≤k≤n, 0≤a[i]<m；
算法知识视频讲解
添加回答
Oxygen_K头像 Oxygen_K
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void xz(char *a,int &n)
{
int i;
//printf("$$$$%s\n", b + 1);
for (i = 1; i <= n; i++)
{
a[i - 1] = a[i];
}
a[n] = a[0];
}

int main()
{
int n, m, k;
char *a,*b;
int num;
int i,j;
while (scanf("%d %d %d", &n, &m, &k) != EOF)
{
a = (char*)malloc(n*sizeof(char));
b = (char*)malloc(n*sizeof(char));
for (i = 1; i <= n; i++)
{
scanf("%d", &num);
a[i] = (char)(num + 48);
}
a[i] = '\0';
for (i = 0; i < m; i++)
{
for (j = 1; j <= n; j++)
{
if (i == 0)
a[j] = a[j] + 0;
else
a[j] = a[j] + 1;
num = (a[j] - '0') % m;
a[j] = (char)(num + 48);
}
strcpy(b + 1, a + 1);
//printf("%s\n", b + 1);
for (j = 0; j < n; j++)
{
xz(a, n);
if (strcmp(b + 1, a + 1) == 1)
{
strcpy(b + 1, a + 1);
}
}
printf("%d\n", b[k] - 48);

}
}
return 0;
}
//这是不对的但是 哪里不对求大神们告知
发表于 2017-08-28 19:59:00 回复(1)
提交观点

问题信息

二分 哈希
上传者：牛客301599号
难度：
1条回答 1594浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号