根据上排给出十个数

根据上排给出十个数，在其下排填出对应的十个数.\ 要求下排每个数都是先前上排那十个数在下排出现的次数。

\#include "stdafx.h"\ /\*\ 给你10分钟时间，根据上排给出十个数，在其下排填出对应的十个数 \ 要求下排每个数都是先前上排那十个数在下排出现的次数。 \ 上排的十个数如下： \ 【0，1，2，3，4，5，6，7，8，9】\ \ 举一个例子， \ 数值: 0,1,2,3,4,5,6,7,8,9 \ 分配: 6,2,1,0,0,0,1,0,0,0 \ 0在下排出现了6次，1在下排出现了2次， \ 2在下排出现了1次，3在下排出现了0次![](http://www.cppblog.com/Images/dot.gif). \ 以此类推.. \ \ 解题思路：关键是理解“要求下排每个数都是先前上排那十个数在下排出现的次数”。\ \ 做以下分析：设总共有n个数，上排a[0![](http://www.cppblog.com/Images/dot.gif)n-1],下排b[0![](http://www.cppblog.com/Images/dot.gif)n-1]，。\ \ 1）下排n个数的累加和为n，即b[0]+b[1]+![](http://www.cppblog.com/Images/dot.gif)+b[n-1] = n\ \ 2）ai\*bi的累加和也为n，即a[0]\*b[0]+a[1]\*b[1]+![](http://www.cppblog.com/Images/dot.gif)+a[n-1]\*b[n-1] = n\ \ 3）对于b中任意一个元素b[j], 都存在i，a[i] = b[j].\ \ 4）对于b中任意一个元素b[j],都有b[j] \>= 0\ \ 5）如果a中存在负数。其在b中出现的次数一定为0. 如果a中数值大于n，则其出现次数也为0.\ \ 6）a中至少有两个非0数值在b中出现的次数非0\ \ a：由1）b[0]+b[1]+...+b[n-1] = n \> n\*b[i],其中b[i]为最小值，则a b中一定均有数值0，否则无解。设a[0] = 0,b[0]为a[0]在b中出现次数。\ \ b：由于b中一定存在0，则0的出现次数一定大于0，因此b[0]\>0 且b[0] \< n，b[1![](http://www.cppblog.com/Images/dot.gif)n-1]中至少一个值为0. 非0元素出现的次数一共是n-b[0].\ \ c：有2）和6）对任意a[i],a[i]\*b[i] \< n，即b[i] \< n/a[i]，对所有a[i]\>=n/2的元素中，在b中出现的次数必须最多只有1个出现次数不为0，且为1.其余出现次数均为0，即[1, n/2）范围内最多只有n/2-1个元素，故0出现的次数必不小于n/2, [n/2,n）范围内的元素必有一个出现次数为1。因此a数列中也必须有1，否则无解。\ \ d：有c得在数值范围为（0，n/2)中（假设有x这样的数）出现的次数和s为n - b[0]或n-b[0]-1。其中1出现的次数至少为1（由c得）。又如果1出现的次数为1，则1出现的次数已经为2，故1出现的次数必大于1.设为x，则x出现的次数至少为1，而x\>1,如果x出现的次数大于1，那么必须要有其他数出现的次数为x，这样无法收敛。故x出现的次数只能为1，1出现的次数只能为2.\ \ 结论：\ \ 0出现的次数为n-4，1出现的次数为2.2出现的次数为1。n-4出现的次数为1.如果数列中无则四个数，无解。\ \*/\ int GetFrequency( int place, int n, int bottom[] ){\ int iCount = 0;\ for( int i = 0; i \< n; i++ )\ if( place == bottom[i] )\ iCount++;\ return iCount;\ }\ \ void SetValid( int arr[], int n, int bottom[] ){\ bool bChanged = true;\ while( bChanged )\ {\ bChanged = false;\ int i = 0;\ for( ; i \< n; i++ )\ {\ int freq = GetFrequency( arr[i], n, bottom );\ if( bottom[i] != freq ){\ bottom[i] = freq;\ bChanged = true;\ }\ }\ }\ \ copy( &bottom[0], &bottom[n], ostream\_iterator\<int\>(cout, " ") );\ cout \<\< endl;\ }\ \ int main(){\ const int C\_SIZE = 10;\ int arr[C\_SIZE] = { 0, 5, 10, 3, 4, 11, 6, 7, 8, 9 };\ int bottom[C\_SIZE];\ memset( bottom, 0, sizeof(int)\*C\_SIZE );\ \ SetValid( arr, C\_SIZE, bottom );\ \ }

软件工具

编程开发

errors

左右互搏

点滴知识

数据结构与算法

undo

todo

标签

software 159

framework 14

hacker 4

php 6

android 64

back-end 11

block-chain 12

cpp 1

cocos2dx 22

error-unresolved 92

lua 9

operating-system 1

python 3

unity3d 32

algorithm 86

assembly 2

css 2

c＃ 3

html 1

javascript 2

kotlin 1

solidity 2

golang 1

game-engine 57

objective-c 2

seo 1

undo 1

java 59

c＋＋ 43

normal-knowledge 22

mac 7

ios 12

game-design 15

Bootstrap 1

CentOS 1

ETCD 1

Kafka 1

database 4

go 2

mysql 1

易语言 1

team 1

app 1

log 1

dropbox 2

SDK 1

h5 1

btc 9

web 4

protocol 1

googleplay 1

pay 1

root 1

html5 1

loom-network 1

metamask 2

blockchain 5

js 3

tools 2

c++ 2

domain 1

宝塔 1

server 2

quick-cocos2d-x 1

spider 1

jailbreak 2

tool 1

rom 1

gateway 1

git 2

github 1