如何看待2017百度校招海量题目2017多益网络笔试题目

来源：蜘蛛抓取(WebSpider) 时间：2016-10-15 09:07 标签： 比亚迪笔试题目2017
给定随机数组a[N]（可能包含重复数字）,要求对它进行排序。其中排序操作只有一种：将任意一个元素移动到数组末尾。问：最少进行几次操作才能完成任务。
这是一道贪心问题
对于数组中的第i个元素，如果它后面有比它小的元素，这就说明第i个元素理应被移动到末尾去。
另外，应该优先移动较小的元素，这样才能够保证较小元素最后排在最前面。
实际上，这个问题没这么复杂。
用一个备份数组b，把a中元素放到b中，对b数组进行排序。从第一个排好序的元素开始，即最小的元素开始与没排好序数组元素比较，检查有多少个已经是从最小到大好序的，位置可以不连续，但是大的元素必须在小的元素后面，统计出一共有 count个，这些元素是不需要移动的元素，一共有 n 个元素，所以需要移动 n - count 次
#include&stdio.h&
#include&math.h&
#include&time.h&
#include&stdlib.h&
#include&iostream&
#include&algorithm&
#include&math.h&
using namespace
int a[1000];
bool has(int x){
for (int i = x + 1; i & N; i++){
if (a[i] & a[x])return true;
return false;
int find(){
int ans = N;
for (int i = 0; i & N; i++){
if (has(i)){
if (a[ans]&a[i])ans =
void op(int x){
int t = a[x];
for (int i = i & N - 1; i++)a[i] = a[i + 1];
a[N - 1] =
int main(){
//freopen(&in.txt&, &r&, stdin);
for (int i = 0; i & N; i++){ cin && a[i]; }
a[N] = 0xfffffff;
int ans = 0;
while (true){
int pos = find();
if (pos == N)break;
cout && ans &&
0~N-1共N个数字有N!种排列方式，对于每一个排列，可以用大于号、小于号将他们连起来，例如：
1&2&4&3&6&5
现在的问题是，只允许用K个小于号把排列连起来，问在这N!种排列中有多少种排列满足小于号的个数不超过K.
这个问题是一道动态规划，f(n,k)表示0~n之间用k个小于号的排列个数，那么，考虑f(n,k)的计算，f(n,k)肯定来源于f(n-1,k)。
对于新来的数字n，考虑将它安排在什么位置:
安排在开头，只需要添加一个大于号
f(n,k)=f(n-1,k)
安排在结尾，只需要添加一个小于号
f(n,k)=f(n-1,k-1)
安排在某个小于号上，a&b变为a&n&b，只需要添加一个大于号
f(n,k)=f(n-1,k)*k
乘以k表示有k个小于号可以选择来进行替换
安排在某个大于号上，a&b变为a&n&b只需要添加一个小于号
f(n,k)=f(n-1,k-1)*(n-k-1)
从0到n-1一共n-2个符号，有k-1个小于号，所以一共有(n-2)-(k-1)=n-k-1个大于号可供选择
这么简单的动态规划我竟然没想到，真是生锈了。
#include&stdio.h&
#include&stdlib.h&
#include&iostream&
#include&algorithm&
#include&math.h&
#include&string.h&
using namespace
int a[1007][1007];
int main(){
//freopen(&in.txt&, &r&, stdin);
cin && n &&
memset(a, 0, sizeof(a));
for (int i = 0; i & i++)a[i][0] = 1;
for (int i = 1; i & i++){
for (int j = 1; j &= j++){
a[i][j] = a[i - 1][j - 1]//放在末尾，需要占用一个小于号
+ a[i - 1][j]//放在开头，只要添加一个大于号
+ a[i - 1][j] * j//放在小于号上，相当于添加一个大于号
+ a[i - 1][j-1] * (i - j);//放在大于号上，相当于添加一个小于号
a[i][j] %= 2017;
cout && a[n-1][k] &&
阅读(...) 评论()如何看待2017百度校招海量题目笔试？ - 知乎22被浏览5715分享邀请回答1添加评论分享收藏感谢收起0添加评论分享收藏感谢收起查看更多回答如何看待2017百度校招海量题目笔试？ - 知乎22被浏览5715分享邀请回答1添加评论分享收藏感谢收起0添加评论分享收藏感谢收起查看更多回答

我要回帖

更多关于 比亚迪笔试题目2017 的文章

 

随机推荐