第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。