第3章〓穷举法























3.1LintCode1068——寻找数组的
中心索引★

问题描述: 给定一个整数数组nums，设计一个算法返回此数组的“中心索引”。中心索引定义为这样的元素，该元素左边的数字之和等于其右边的数字之和。如果不存在这样的中心索引，返回-1；  如果有多个中心索引，返回最左侧的那一个。例如，nums={1, 7, 3, 6, 5, 6}，答案是 3，因为nums［3］元素的左边和右边的数字之和均为11。要求设计如下成员函数: 

int pivotIndex(vector<int> &nums) { }


解法1: 采用直接穷举法，对于每个元素nums［i］，求左边元素的和left以及右边元素的和right，若left=right，则返回i。最后返回-1。对应的程序如下: 

class Solution {

public:

int pivotIndex(vector<int> &nums) {

int n=nums.size();

int left,right;

for (int i=0;i<n;i++) {

left=0;

for(int j=0;j<i;j++)

left+=nums［j］;

right=0;

for(int j=i+1;j<n;j++)

right+=nums［j］;

if (right==left)

return i;

}

return -1;

}

};


上述算法的时间复杂度为O(n2)，程序提交时超时（time limit exceeded）。

解法2: 在枚举nums［i］时，左边元素的和left是依次求出的，例如求出nums［i-1］的left，则nums［i］的left等于left+nums［i-1］。另外可以事先求出全部元素的和sum，当nums［i］对应的左边元素的和为left时，则右边元素的和等于sum-left-nums［i］，这样算法的时间复杂度降为O(n)。对应的程序如下: 

#include<numeric>

class Solution {

public:

int pivotIndex(vector<int> &nums) {

int n=nums.size();

int sum=accumulate(nums.begin(),nums.end(),0);

int left=0,right;

for (int i=0;i<n;i++) {

if (i!=0)

left+=nums［i-1］;

right=sum-left-nums［i］;

if (right==left)

return i;

}

return -1;

}

};


上述程序提交后通过，执行用时为81ms，内存消耗为5.37MB。

3.2LintCode1517——最大子数组★
问题描述: 给定一个由n个整数构成的数组A和一个整数K（1≤K≤n≤100），设计一个算法从所有长度为K的A的连续子数组中返回最大的连续子数组，如果两个数组中第一个不相等的元素在A中的值大于B中的值，则定义子数组A大于子数组B。例如，A={1，2，4，3}，B={1，2，3，5}，则A大于B，因为A［2］>B［2］。要求设计如下成员函数: 

vector<int> largestSubarray(vector<int> &A, int K) {


解法1: 采用穷举法，首先取A的前K个元素存放在ans中作为答案，然后直接枚举每个子数组A［i..j］，若其长度等于K，则与ans比较大小将较大者存放在ans中，最后返回ans即可。对应的程序如下: 

class Solution {

public:

vector<int> largestSubarray(vector<int> &A, int K) {

int n=A.size();

if(n<K) return {};

vector<int> ans;

ans=vector<int>(A.begin(),A.begin()+K);

for(int i=0;i<n;i++) {

for(int j=i;j<n;j++) {

if(j-i+1==K) {

vector<int> cura=vector<int>(A.begin()+i,A.begin()+j+1);

if(cura>ans) ans=cura;

}

}

}

return ans;

}

};

上述程序提交后通过，执行用时为41ms，内存消耗为5.53MB。

解法2: 由于这里的比较对象是长度为K的子数组，而子数组的K个元素是相邻的，所以改为用i直接枚举子数组A［i..i+K-1］即可，这样算法的时间复杂度降为O(n)。对应的程序如下: 

class Solution {

public:

vector<int> largestSubarray(vector<int> &A, int K) {

int n=A.size();

if(n<K) return {};

vector<int> ans;

ans=vector<int>(A.begin(),A.begin()+K);

for(int i=0;i<n-K+1;i++) {

vector<int> cura=vector<int>(A.begin()+i,A.begin()+i+K);

if(cura>ans) ans=cura;

}

return ans;

}

};


上述程序提交后通过，执行用时为41ms，内存消耗为4.76MB。

3.3LintCode1338——停车困境★
问题描述: 停车位是一条很长的直线，每米都有一个停车位，停车场里停着n（1≤n≤105）辆小车，所有车位上面的车都是唯一的，用cars表示。现在要通过建造遮雨棚来遮雨、挡雨，要求至少有k（1≤k≤n）辆小车的车顶被遮雨棚遮盖，设计一个算法求遮雨棚遮盖k辆小车的车顶需要的最小长度。例如，cars={2，10，8，17}，k=3，答案是9，即建造长度为9的遮雨棚，遮盖从第2个到第10个的所有停车位。要求设计如下成员函数: 

int ParkingDilemma(vector<int> &cars, int k) { }


解: 如果直接采用穷举法会超时，改进方法是将cars递增排序，然后将每k个元素看成一个遮雨棚（恰好遮盖k辆小车），求出其长度，通过比较求最小长度ans。例如，cars={2，10，8，17}、k=3时求遮雨棚的最小长度如图3.1所示。对应的程序如下: 

class Solution {

const int INF=0x3f3f3f3f;

public:

int ParkingDilemma(vector<int> &cars, int k) {

sort(cars.begin(),cars.end());

int ans=INF;

for (int i=0;i<cars.size()-k+1;i++) {

ans=min(ans,cars［i+k-1］-cars［i］+1);

}

return ans;

}

};




图3.1k=3时遮雨棚的最小长度



上述程序提交后通过，执行用时为41ms，内存消耗为5.44MB。

3.4LintCode993——数组划分Ⅰ★
问题描述: 给定一个有2n个整数的数组nums，设计一个算法把这些整数分成n组，例如(a1，b1)、(a2，b2)、……、(an，bn)，并且使i从1到n的min(ai，bi)之和尽可能大。其中n是一个范围为［1，10000］的正整数，数组中元素的范围为［-10000，10000］。例如，nums={1，4，3，2}，答案是4，这里n=2，数组中的元素分为数对(1，2)和(3，4)。要求设计如下成员函数: 

int arrayPairSum(vector<int> &nums) { }


解: 如果直接采用穷举法会超时，改进方法是将数组nums递增排序，取出所有下标为偶数的元素求和。例如，nums={1，4，3，2}，排序后nums={1，2，3，4}，依次两两一组的结果满足题目要求，每组的最小值即该组的前一个元素，取出1和3并且累计，结果为4。对应的程序如下: 

class Solution {

public:

int arrayPairSum(vector<int> &nums) {

sort(nums.begin(),nums.end());

int ans=0;

for (int i=0;i<nums.size();i+=2)

ans+=nums［i］;

return ans;

}

};


上述程序提交后通过，执行用时为61ms，内存消耗为5.48MB。

3.5LintCode406——和大于s的最
小子数组★★

问题描述: 给定一个由n个正整数组成的数组和一个正整数s，设计一个算法求满足其和大于或等于s的最小长度的子数组，如果无解则返回-1。例如，nums={2，3，1，2，4，3}，s=7，答案是2，因为子数组{4，3}是该条件下的最小长度子数组。要求设计如下成员函数: 

int minimumSize(vector<int> &nums, int s) { }


解法1: 如果直接枚举nums［i..j］，求出元素和sum，当sum≥s时求最小长度j-i+1，时间复杂度为O(n3)，一定会出现超时。改为用前缀和数组，设psum［i］为nums中前i+1个元素的和，在求出psum数组后，有nums［i+1..j］的元素和等于psum［j］-psum［i］，这样通过枚举i和j求出元素和大于或等于s的最小子数组长度j-i。对应的程序如下: 

class Solution {

public:

int minimumSize(vector<int> &nums, int s) {

int n=nums.size();

if(n==0) return -1;

int psum［n］;

psum［0］=nums［0］;

for(int i=1;i<n;i++)

psum［i］=psum［i-1］+nums［i］;

int ans=n+1;								　　//存放答案，取最大值

for(int i=-1;i<n-1;i++) {

for(int j=i;j<n;j++) {

int sum=psum［j］-psum［i］;    　　//求nums［i+1..j］的元素之和

if(sum>=s) ans=min(ans,j-i);

}

}

if(ans==n+1)return -1;

else return ans;

}

};


上述算法的时间复杂度为O(n2)，程序提交时仍然超时（time limit exceeded）。

解法2: 用i、j两个指针表示一个窗口为nums［i-1..j-1］（i、j均从0开始表示初始窗口为空），先保持i不变通过后移j找到元素和大于或等于s的窗口nums［i..j］，若不存在这样的窗口则结束，找到这样的窗口后i后移缩小窗口，但始终保证窗口的元素和不小于s，在所有这样的窗口中求最小长度。例如，nums={2，3，1，2，4，3}，s=7，首先置ans=7，i=0，j=0，求解过程如下: 

（1） j后移到等于4，找到sum为2+3+1+2=8，此时sum≥s，再后移i同时从sum中减去nums［i］直到sum<s，此时i=1（sum为8-2=6），说明nums［i-1..j-1］即nums［0..3］是一个满足要求的窗口，长度为4，置ans=4。

（2） i=1，j=4，sum=6，后移到j=5，找到sum为6+4=10，此时sum≥s，再后移i同时从sum中减去nums［i］直到sum<s，此时i=3（sum为10-3-1=6），说明nums［i-1..j-1］即nums［2..4］是一个满足要求的窗口，长度为3，置ans=3。

（3） i=3，j=5，sum=6，后移到j=6，找到sum为6+3=9，此时sum≥s，再后移i同时从sum中减去nums［i］直到sum<s，此时i=5（sum为9-2-4=3），说明nums［i-1..j-1］即nums［4..5］是一个满足要求的窗口，长度为2，置ans=2。

最终结果是ans=2，返回2。对应的程序如下: 

class Solution {

public:

int minimumSize(vector<int> &nums, int s) {

int n=nums.size();

int ans=n+1;						　　//存放答案，取最大值

int i=0, j=0;

int sum=0;

while (j<n) {

while (j<n && sum<s)		　　//扩大窗口

sum+=nums［j++］;

if (sum<s) break;

while (i<j && sum>=s)	　　//缩小窗口

sum-= nums［i++］;

ans=min(ans, j-i+1);

}

if (ans==n+1)	return -1;

else return ans;

}

};


在上述算法中i、j指针均后移，时间复杂度为O(n)。上述程序提交后通过，执行用时为163ms，内存消耗为20.55MB。

3.6LintCode1331——英语软件★
问题描述: 小林是班级的英语课代表，他想开发一款软件处理班上同学的成绩（所有成绩在0～100的范围内）。小林的软件有一个神奇的功能，能够通过一个百分数来反映各同学的成绩在班上的位置，即“成绩超过班级多少百分比的同学”。设这个百分比为p，某同学考了s分，则可以通过p=(分数不超过s的人数-1)/班级总人数×100%计算出p。请帮助小林设计一下这个软件。其中score数组表示所有同学的成绩，score［i］表示第一个同学的成绩，ask数组中的ask［i］表示询问ask［i］个人的成绩百分比，每询问一次输出对应的成绩百分比，不需要输出百分号，答案向下取整（为避免精度丢失，优先计算乘法）。例如，score={100，98，87}，ask={1，2，3}，表示共有3个人，第一个人到第三个人的成绩分别是100、98和97，要求求出第一个人到第三个人的成绩百分比，答案是{66，33，0}，即第一个人的成绩为100，超过了66%的学生。要求设计如下成员函数: 

vector<int> englishSoftware(vector<int> &score, vector<int> &ask) { }


解: 这里采用前缀和数组psum，先遍历score求出成绩为s的人数psum［s］，再通过遍历psum并计算psum［i］+=psum［i-1］求出分数小于或等于s的人数psum［s］。这样对于序号ask［i］，对应的成绩百分比为rnk=(psum［score［ask［i］-1］］-1)×100/n，将其添加到ans中，最后返回ans即可。对应的程序如下: 

class Solution {

public:

vector<int> englishSoftware(vector<int> &score, vector<int> &ask) {

int n=score.size();

vector<int> psum(101,0);

for(int s:score)

psum［s］++;

for(int i=1;i<101;i++)

psum［i］+=psum［i-1］;

vector<int> ans;

for(int i=0;i<ask.size();i++) {

int rnk=(psum［score［ask［i］-1］］-1)*100/n;

ans.push_back(rnk);

}

return ans;

}

};


上述程序提交后通过，执行用时为41ms，内存消耗为2.29MB。

3.7LintCode397——最长上升连续
子序列★

问题描述: 给定一个长度为n的整数数组A，其中所有元素是唯一的，设计一个算法找出该数组中的最长上升连续子序列（LICS），这里的最长上升连续子序列可以定义为从右到左或从左到右的序列。例如，A={5，4，2，1，3}，答案是4，其最长上升连续子序列为{5，4，2，1}； A={5，1，2，3，4}，答案是4，其最长上升连续子序列为{1，2，3，4}。要求设计如下成员函数: 

int longestIncreasingContinuousSubsequence(vector<int> &A) { }


解: 用ans存放答案（初始为0），用incnt和decnt分别表示递增和递减连续子序列的长度（初始均为1），用i从1开始遍历A，若A［i-1］<A［i］，则执行incnt++和decnt=1，否则执行decnt++和incnt=1，然后在ans、incnt和decnt中取最大值存放到ans中。遍历完毕返回ans即可。对应的程序如下: 

class Solution {

public:

int longestIncreasingContinuousSubsequence(vector<int> &A) {

int n=A.size();

if (n<=2) return n;

int incnt=1;

int decnt=1;

int ans=0;

for (int i=1;i<n;i++) {

if (A［i-1］<A［i］) {

incnt++;

decnt=1;

}

else if (A［i-1］>A［i］) {

decnt++;

incnt=1;

}

ans=max(ans, decnt);

ans=max(ans, incnt);

}

return ans;

}

};


上述程序提交后通过，执行用时为41ms，内存消耗为4.3MB。

3.8LeetCode1534——统计好三元组★
问题描述: 给定一个含n（3≤n≤100）个整数的数组arr，以及 a、b、c 三个整数，设计一个算法求其中好三元组的数量。如果三元组（arr［i］，arr［j］，arr［k］）满足下列全部条件，则认为它是一个好三元组: 

（1） 0≤i<j<k<n。

（2） |arr［i］-arr［j］|≤a，|arr［j］-arr［k］|≤b，|arr［i］-arr［k］|≤c。

例如，arr={3，0，1，1，9，7}，a=7，b=2，c=3，答案是4，一共有4个好三元组,即(3，0，1)、(3，0，1)、(3，1，1)和(0，1，1)。要求设计如下成员函数: 

int countGoodTriplets(vector<int>& arr, int a, int b, int c) { }


解: 直接采用简单穷举法，枚举全部情况，累计满足题目要求的好三元组的数量ans，最后返回ans即可。对应的程序如下: 

class Solution {

public:

int countGoodTriplets(vector<int>& arr, int a, int b, int c) {

int n=arr.size();

int ans=0;

for(int i=0;i<n-2;i++) {

for(int j=i+1;j<n-1;j++) {

for(int k=j+1;k<n;k++) {

if(abs(arr［i］-arr［j］)<=a && abs(arr［j］-arr［k］)<=b && abs(arr［i］-arr［k］)<=c)

ans++;

}

}

}

return ans;

}

};


上述程序提交后通过，执行用时为48ms，内存消耗为8MB。

3.9LeetCode204——计数质数★★
问题描述: 给定一个整数n（0≤n≤5×106），设计一个算法求所有小于非负整数n的质数的个数。例如，n=10，答案是4，小于10的质数是2、3、5、7。要求设计如下成员函数: 

int countPrimes(int n) { }


解: 如果直接采用穷举法判断1～n的每个整数是否为质数，并累计其中质数的个数，这样一定会超时。这里采用质数筛选法，对于质数i，则i的i倍整数、i+1倍整数等一定不是质数，再累计其中质数的个数ans，最后返回ans即可。对应的程序如下: 

class Solution {

public:

int countPrimes(int n) {

bool prime［n+1］;								　　//prime［i］表示整数i是否为质数

memset(prime,true,sizeof(prime));		　　//预设均为质数

for(int i=2;i*i<n;i++) {

if(prime［i］) {								　　//i是质数，置其倍数为非质数

for(int j=i*i;j<n;j+=i) prime［j］=false;

}

}

int ans=0;

for(int i=2;i<n;i++) {						　　//累计质数的个数

if(prime［i］) ans++;

}

return ans;

}

};


上述程序提交后通过，执行用时为148ms，内存消耗为11.3MB。

3.10LeetCode187——重复的DNA
序列★★


问题描述: DNA序列由一系列核苷酸组成，给定一个表示DNA序列的字符串 s，设计一个算法返回在DNA分子中出现不止一次的长度为10的所有序列（子字符串），可以按任意顺序返回。例如，输入s ="AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"，答案是{"AAAAACCCCC","CCCCCAAAAA"}。要求设计如下成员函数: 

vector<string> findRepeatedDnaSequences(string s) { }


解: 采用简单穷举法，用unordered_map<string,int>类型的哈希表cntmap实现子字符串的计数，用ans存放答案。i从0开始遍历s，提取当前长度为10的子串ss，累计其个数，若个数为2将其添加到ans中。遍历完毕返回ans即可。对应的程序如下: 

class Solution {

public:

vector<string> findRepeatedDnaSequences(string s) {

vector<string> ans;

unordered_map<string,int> cntmap;

int n=s.size();

if(n<10) return ans;

for(int i=0;i<n-9;i++) {

string ss=s.substr(i,10);

cntmap［ss］++;

if(cntmap［ss］==2)

ans.push_back(ss);

}

return ans;

}

};


上述程序提交后通过，执行用时为52ms，内存消耗为22.9MB。

3.11LeetCode2018——判断单词是否能放
入填字游戏内★★


问题描述: 给定一个m×n的矩阵board，它代表一个填字游戏的当前状态。在填字游戏的格子中包含小写英文字母（已填入的单词）、表示空格的" "和表示障碍格子的"#"。如果满足以下条件，则可以水平（从左到右或者从右到左）或竖直 （从上到下或者从下到上）填入一个单词: 

（1） 该单词不占据任何'#'对应的格子。

（2） 每个字母对应的格子要么是" "（空格）要么与 board 中已有字母的匹配。

（3） 若单词是水平放置，则该单词左边和右边相邻的格子（可以是边缘）不能为" "或小写英文字母。

（4） 若单词是竖直放置，则该单词上边和下边相邻的格子（可以是边缘）不能为" "或小写英文字母。

给定一个字符串word，设计一个算法当word可以被放入board中时返回 true，否则返回false。例如，board={{"#"，" "，"#"}，{" "，" "，"#"}，{"#"，"c"，" "}}，word="abc"，答案为true，因为word可以放在中间一列。要求设计如下成员函数: 

bool placeWordInCrossword(vector<vector<char>>& board, string word) { }


解: 假设word的长度为len，首先找到一个非"#"的位置（i，j），试探沿着di方向是否能够放置word，可以放置的条件检测如下。

（1） 位置（i，j）的di反方向位置一定是"#"，即检测首位置的di方向上的前一个位置是否满足条件（3）。

（2） 位置（i，j）的di方向的后面第len-1个位置是存在的，如果存在后面第len个位置，则该位置必须是"#"，即检测尾位置的di方向上的后一个位置是否满足条件（3）。

（3） word是否可以从（i，j）位置开始放置，直到放置完毕。

如果上述条件均满足，返回true，否则试探位置（i，j）的其他方位，若位置（i，j）试探完毕，则找到其他非"#"的位置继续试探，全部试探完毕返回false。对应的程序如下: 

class Solution {

public:

bool placeWordInCrossword(vector<vector<char>>& board, string word) {

int dx［］={0,1,0,-1};                    						　　//水平方向的偏移量(顺时针方向)

int dy［］={1,0,-1,0};                   								 //垂直方向的偏移量

int len=word.size();

int m=board.size(),n=board［0］.size();

for (int i=0;i<m;i++) {

for (int j=0;j<n;j++) {

if (board［i］［j］=='#') continue;     				　　//单词不能占据'#'

for (int di=0;di<4;di++) {

int xx=i+dx［(di+2)%4］; 

int yy=j+dy［(di+2)%4］;

if (xx>=0 && xx<m && yy>=0 && yy<n) {

if (board［xx］［yy］!='#')     					　　//首位置的条件(3)检测

continue;

}

xx=i+dx［di］*(len-1);

yy=j+dy［di］*(len-1);

if (xx<0 || xx>=m || yy<0 || yy>=n)			　　//超界时跳过

continue;

xx+=dx［di］; yy+=dy［di］;

if (xx>=0 && xx<m && yy>=0 && yy<n) {

if (board［xx］［yy］!='#') 						　　//尾位置的条件（3）检测

continue;

}

bool flag=true;

for (int k=len-1;k>=0;k--) {    				　　//检测中间是否匹配

xx-=dx［di］;

yy-=dy［di］;

if (board［xx］［yy］!=' ' && board［xx］［yy］!=word［k］) {

flag=false;

break;

}

}

if (flag) return true;

}

}

}

return false;

}

};


上述程序提交后通过，执行用时为160ms，内存消耗为58.3MB。

3.12LeetCode2151——基于陈述统计最多
好人数★★★

问题描述: 游戏中存在两种角色，即好人（该角色只说真话）和坏人（该角色可能说真话，也可能说假话）。给定一个n×n（2≤n≤15）的二维整数数组statements，表示n个玩家对彼此角色的陈述。具体来说，statements［i］［j］ 可以是下列值之一: 0表示i的陈述认为j是坏人，1表示i的陈述认为j是好人，2表示i没有对j作出陈述。玩家不会对自己进行陈述，即对所有statements［i］［i］=2。设计一个算法根据这n个玩家的陈述求可以认为是好人的最大数目。要求设计如下成员函数: 

int maximumGood(vector<vector<int>> &statements) { }


解: 在n个人中每个人都可能是好人或者坏人，这样有2n种情况，每种情况用一个子集表示。例如n=3时，3个人的编号为0～2，有23=8种情况，每种情况用3个二进制位表示，0表示坏人，1表示好人，如二进制数101表示玩家0和2是好人，玩家1是坏人。这样恰好用十进制数0～2n-1表示全部情况。

对于每种情况s，用sum累计好人的人数（初始为0），遍历s的每一位，若某一位i是1，说明玩家i是好人，所谓好人只说真话，也就是说若statements［i］［j］<2成立（说明玩家i对玩家j有陈述），而在情况s中玩家j的好人值为(s>>j)&1，若两者不相等，说明情况s是矛盾的，忽略该情况。如果情况s中每个好人和实际陈述相符，则累计其中好人的个数sum，在所有这样的情况中通过比较求最大sum。对应的程序如下: 

class Solution {

public:

int maximumGood(vector<vector<int>> &statements) {

int n=statements.size();

int ans=0;

for (int s=1;s<1<<n;s++) {

int sum=0;                          				　　//子集s中好人的个数

for (int i=0;i<n;i++) {

if ((s>>i)&1) {                 			　　//枚举s中的好人i

for (int j=0;j<n;j++) {     			　　//枚举i的所有陈述

if (statements［i］［j］<2 && statements［i］［j］!=((s>>j)&1)) { 

goto next;							 //该陈述与s中的情况矛盾则忽略s

}

}

sum++;

}

}

ans=max(ans,sum);

next:;

}

return ans;

}

};


上述程序提交后通过，执行用时为96ms，内存消耗为8.2MB。

3.13POJ2000——金币
时间限制: 1000ms，空间限制: 30000KB。

问题描述: 国王向忠诚的骑士支付金币，第一天支付给骑士一枚金币，在接下来的两天（第二天和第三天）中每一天支付给骑士两枚金币，在接下来的3天（第四天、第五天和第六天）中每一天支付给骑士3枚金币，在接下来的4天（第七天、第八天、第九天和第十天）中每一天支付给骑士4枚金币。这种支付模式将无限期地继续下去，即在连续n天每天收到n个金币后，骑士将在接下来的n+1天连续收到n+1个金币，其中n为任意正整数。设计一个算法，计算在给定天数内（从第一天开始）国王支付给骑士的金币总数。

输入格式: 输入至少包含一行，但不超过21行。输入的每一行（最后一行除外）都包含一个测试用例的数据，仅包含一个表示天数的整数（范围为1～10000），输入的结束由包含数字0的行表示。

输出格式: 每个测试用例只有一行输出，这一行包含来自输入行的天数，后跟一个空格以及在给定天数内支付给骑士的金币总数，从第一天开始。

输入样例: 

10

6

7

11

15

16

100

10000

1000

21

22

0


输出样例: 

10 30

6 14

7 18

11 35

15 55

16 61

100 945

10000 942820

1000 29820

21 91

22 98


解: 如果简单地枚举每一天的金币数可能超时，改进方法是将金币数相同的若干天看成一个段，先求出n天对应的前一个段的天数pred，累计到pred为止的金币数sum，第n天对应段的每天金币数为coin，则答案等于sum+(n-pred)*coin。

例如，n=16，如表3.1所示，对应的段号为6，该段的每天金币数coin=6，前一个段号为5，前面5个段的总金币数sum为1×1+2×2+3×3+4×4+5×5=55，前面5个段的总天数pred=15，答案为sum+(n-pred)×coin=55+1×6=61。


表3.1n=16时的计算过程



段号
1
2
3
4
5
6

天
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
金币
1
2
2
3
3
3
4
4
4
4
5
5
5
5
5
6
合并
1×1
2×2
3×3
4×4
5×5



对应的程序如下: 

#include<iostream>

using namespace std;

int Coins(int n) {

if (n==1) return 1;

int coin=1;

int sum=1;

int d=1;

int pred;

while (d<n) {

if (coin>1)

sum+=coin*coin;

coin++;

pred=d;

d+=coin;

}

return sum+(n-pred)*coin;

}

int main() {

int n;

cin >> n;					　　//读入第一个测试用例

while (n>0) {

cout << n << " " << Coins(n) << endl;

cin >> n;				　　//读入下一个测试用例

}

return 0;

}


上述程序提交后通过，执行用时为65ms，内存消耗为176KB。

3.14POJ1013——假币问题
时间限制: 1000ms，空间限制: 10000KB。

问题描述: Sally有12枚银币，其中有11枚真币和一枚假币，假币看起来和真币没有什么区别，只是重量不同。Sally不知道假币比真币轻还是重，于是他向朋友借了一架天平。朋友希望Sally称3次就能找出假币并且确定假币是轻还是重。例如，如果Sally用天平称两枚银币，发现天平平衡，说明两枚都是真的，如果Sally用一枚真币与另一枚银币比较，发现它比真币轻或重，说明它是假币。经过精心安排每次的称量，Sally保证能在称3次后确定假币。

输入格式: 第一行包含整数n，表示测试用例的数目。对于每个测试用例输入3行，每行表示一次称量的结果，Sally事先将银币标号为A～L，每次称量的结果用3个以空格隔开的字符串表示，即天平左边放置的银币、天平右边放置的银币和平衡状态，其中平衡状态用"up"、"down"和"even"表示，分别为左端重、右端重和平衡。天平左右的银币数总是相等的。

输出格式: 输出哪一个标号的银币是假币，并说明它比真币轻还是重（is heavy或者is light）。

输入样例: 

1

ABCD EFGH even	　　//表示ABCD银币的重量等于EFGH银币的重量

ABCI EFJK up		　　//表示ABCI银币的重量大于EFJK银币的重量

ABIJ EFGH even	　　//表示EFGH银币的重量等于EFGH银币的重量


输出样例: 

K is the counterfeit coin and it is light. 


解: 用数组a表示12个银币的重量，真币的重量为0。设计balanced()算法用于判断当12个银币的重量已知时是否满足3次称量的情况。对于每个银币i，置a［i］=-1（假设银币i是较轻的假币），如果balanced()算法返回true说明假设成立，否则置a［i］=1（假设银币i是较重的假币），如果balanced()算法返回true说明假设成立，否则说明银币i是真币，置a［i］=0继续。最后根据成立的假设输出答案。对应的程序如下: 

#include<iostream>

int a［12］;

char left［3］［7］,right［3］［7］,state［3］［7］;

bool balanced() {									　　//判断当前的情况是否满足

for(int i=0;i<3;i++) {							　　//枚举3次称量的情况

int leftw=0,rightw=0;

for(int j=0;left［i］［j］;j++)					　　//求出左端银币的总重量

leftw+=a［left［i］［j］-'A'］;

for(int j=0;right［i］［j］;j++)					　　//求出右端银币的总重量

rightw+=a［right［i］［j］-'A'］;

if(leftw>rightw && state［i］［0］!='u')	　　//违反"up"的称量结果

return false;

if(leftw==rightw && state［i］［0］!='e')	　　//违反"even"的称量结果

return false;

if(leftw<rightw && state［i］［0］!='d')	　　//违反"down"的称量结果

return false;

}

return true;

}

int main() {

int n,no;

scanf("%d",&n);

while (n--) {

for (int i=0;i<3;i++)

scanf("%s%s%s",left［i］,right［i］,state［i］);

for(int i=0;i<12;i++)

a［i］=0;

for(no=0;no<12;no++) {					　　//枚举每个银币

a［no］=1;										　　//假设银币i是较轻的假币

if(balanced()) break;

a［no］=-1;									　　//假设银币i是较重的假币

if(balanced()) break;

a［no］=0;

}

printf("%c is the counterfeit coin and it is %s.＼n",no+'A',a［no］>0?"heavy":"light");

}

return 0;

}


上述程序提交后通过，执行用时为0ms，内存消耗为92KB。

3.15POJ1256——字谜
时间限制: 1000ms，空间限制: 10000KB。

问题描述: 编写一个程序从给定的一组字母中生成所有可能的单词。例如，给定单词"abc"，通过探索3个字母的所有不同组合，输出单词"abc"、"acb"、"bac"、"bca"、"cab"和"cba"。单词中的一些字母可能会出现不止一次，在这样的情况下不应多次生成相同的单词，并且应按字母升序输出单词。

输入格式: 输入由几个单词组成。第一行包含一个数字，表示后面的单词数。以下每一行包含一个单词。一个单词由从A到Z的大写或小写字母组成，大写和小写字母被认为是不同的，每个单词的长度小于13。

输出格式: 对于输入的每个单词，输出应该包含可以使用给定单词的字母生成的所有不同单词，从同一个输入生成的单词应该按字母升序输出。一个大写字母位于相应的小写字母之前。

输入样例: 

3

aAb

abc

acba


输出样例: 

Aab

Aba

aAb

abA

bAa

baA

abc

acb

bac

bca

cab

cba

aabc

aacb

abac

abca

acab

acba

baac

baca

bcaa

caab

caba

cbaa


解: 题目就是要产生字符串str的全排列，需要注意以下两点。

（1） 排列要除重，不会输出重复的排列。

（2） 按字母升序输出，这里的字母升序不是指ASCII码顺序，而是A<a<B<b<C<c，以此类推。

为了简单，采用STL中的next_permutation（）函数枚举排列，该函数具有自动除重功能，为了满足（2），需要制定这样的比较关系: 转换为大写字母相同时按ASCII码比较，例如A<a、B<b等，转换为大写字母不相同时按转换的大写字母比较，例如A<B、A<b、b<C等。对应的程序如下: 

#include<iostream>

#include<string.h>

#include<algorithm>

#define N 14

using namespace std;

char str［N］;

struct Cmp {

bool operator()(char& a,char& b) {			　　//制定比较关系

if(toupper(a)==toupper(b))

return a<b;

else

return toupper(a)<toupper(b);

}

};

int main() {

int n,m;

scanf("%d",&n);

while(n--){

scanf("%s",str);

m=strlen(str);

sort(str,str+m,Cmp());

printf("%s＼n",str);

while(next_permutation(str,str+m,Cmp()))

printf("%s＼n",str);

}

return 0;

}


上述程序提交后通过，执行用时为63ms，内存消耗为92KB。

3.16POJ3187——倒数和
时间限制: 1000ms，空间限制: 65536KB。

问题描述: 有这样一个游戏，以一定的顺序写从1到n（1≤n≤10）的数字，然后将相邻的数字相加以产生一个数字少一个的新列表，重复这个过程，直到只剩下一个数字。例如，游戏的一个实例（当n=4时）可能是这样的: 

3 1 2 4

4 3 6

7 9

16


现在给定n和最后一行的数字，请编写程序输出第一行的数列。

输入格式: 输入一行包含两个以空格分隔的整数，即n和最后一行的数字。

输出格式: 输出第一行的数列，如果有多个这样的数列，选择字典顺序最小的一个。

输入样例: 

4 16


输出样例: 

3 1 2 4


解: 所求答案一定是1～n的某个排列。采用穷举法，用数组a枚举1～n的全部排列（初始a取值为1～n）。对于每个排列a，以其作为第一行，用数组b保存其累计结果，最后一行b［n-1］仅包含一个整数，若b［n-1］［0］=sum，则输出对应的a。为了简单，采用STL中的next_permutation（）函数枚举排列，由于该函数产生的排列是递增的，所以满足要求的第一个a就是最小排列。对应的程序如下: 

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

#define MAXN 11

int main() {

int a［MAXN］;

int n,sum;

scanf("%d %d",&n,&sum);

for(int i=1;i<=n;i++)								　　//产生初始排列1~n

a［i-1］=i;

int b［MAXN］［MAXN］;

memset(b,0,sizeof(b));

do{

for(int i=0;i<n;i++)								　　//由a作为第一行

b［0］［i］=a［i］;

for(int i=1;i<n;i++) {							　　//求出其他n-1行

for(int j=0;j<n-i;j++) {

b［i］［j］=b［i-1］［j］+b［i-1］［j+1］;

}

}

if(b［n-1］［0］==sum) break;						　　//找到满足要求的a

} while(next_permutation(a,a+n));				　　//枚举下一个排列

for(int i=0;i<n;i++) {								　　//输出a

if(i==0) printf("%d",a［i］);

else printf(" %d",a［i］);

}

return 0;

}

上述程序提交后通过，执行用时为63ms，内存消耗为88KB。