首页 > 代码库 > NYOJ139---我排第几个
NYOJ139---我排第几个
我排第几个
时间限制:1000 ms | 内存限制:65535 KB
难度:3
- 描述
现在有"abcdefghijkl”12个字符,将其所有的排列中按字典序排列,给出任意一种排列,说出这个排列在所有的排列中是第几小的?
- 输入
- 第一行有一个整数n(0<n<=10000);
随后有n行,每行是一个排列; - 输出
- 输出一个整数m,占一行,m表示排列是第几位;
- 样例输入
3 abcdefghijkl hgebkflacdji gfkedhjblcia
- 样例输出
1 302715242 260726926
- 来源
- [苗栋栋]原创
- 上传者
苗栋栋
康拓展开的应用
/************************************************************************* > File Name: nyoj139.cpp > Author: ALex > Mail: 405045132@qq.com > Created Time: 2015年01月12日 星期一 21时22分04秒 ************************************************************************/ #include <map> #include <set> #include <queue> #include <stack> #include <vector> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int fn[14]; char str[14]; bool vis[30]; int main() { fn[0] = 1; for (int i = 1; i <= 12; ++i) { fn[i] = fn[i - 1] * i; } int t; scanf("%d", &t); while (t--) { scanf("%s", str); long long ans = 0; memset (vis, 0, sizeof(vis)); for (int i = 0; i < 12; ++i) { int cur = str[i] - 'a' + 1; int cnt = cur - 1; vis[str[i] - 'a' + 1] = 1; for (int j = 0; j < i; ++j) { if (str[j] < str[i] && vis[str[j] - 'a' + 1]) { --cnt; } } ans += (long long)fn[12 - i - 1] * cnt; } printf("%lld\n", ans + 1); } return 0; }
NYOJ139---我排第几个
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。