序
刚做完一套京东的在线笔试，感觉那叫一个惨淡呀，可以说前面的基础知识考的忒宽了点嘛，好多都不会了~~~~(>_<)~~~~
期待两道编程题能通过哦~~~
编程1 -- 选举游戏
题目
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem Description:
小东和其他小朋友正在玩一个关于选举的游戏。选举是通过投票的方式进行的，得票最多的人将获胜。
小东是编号为1的候选者，此外还有其他的候选者参加选举。根据初步的调查情况，所有准备投票的小朋友都有一定的投票倾向性，小东如果要获得胜利，必须争取部分准备为其他候选人投票的小朋友。由于小东的资源较为有限，她希望用最小的代价赢得胜利，请你帮忙计算她最少需要争取的选票数。
输入
输入有若干组，每组包含两行，第一行为一个正整数n（2<=n<=100），表示候选者的数量，第二行为每个候选人预期得到的选票数，以空格分开，每人的预期得票数在1到1000之间（包含1和1000）。
经过小东的争取后，可能出现候选人得票数为0或超过1000的情况。
输出
对每组测试数据，单独输出一行，内容为小东最少需要争取的选票数。
样例输入
5
5 1 11 2 8
4
1 8 8 8
2
7 6
样例输出
4
6
0
Problem Description:
小东和其他小朋友正在玩一个关于选举的游戏。选举是通过投票的方式进行的，得票最多的人将获胜。
小东是编号为1的候选者，此外还有其他的候选者参加选举。根据初步的调查情况，所有准备投票的小朋友都有一定的投票倾向性，小东如果要获得胜利，必须争取部分准备为其他候选人投票的小朋友。由于小东的资源较为有限，她希望用最小的代价赢得胜利，请你帮忙计算她最少需要争取的选票数。
输入
输入有若干组，每组包含两行，第一行为一个正整数n（2<=n<=100），表示候选者的数量，第二行为每个候选人预期得到的选票数，以空格分开，每人的预期得票数在1到1000之间（包含1和1000）。
经过小东的争取后，可能出现候选人得票数为0或超过1000的情况。
输出
对每组测试数据，单独输出一行，内容为小东最少需要争取的选票数。
样例输入
5
5 1 11 2 8
4
1 8 8 8
2
7 6
样例输出
4
6
0
分析
这道题还是不难哒，循环查找序列中最大值，直到最大值所在的索引为0（代表小东）；当最大值索引不是0时，最大值元素递减，首元素（索引0）递增，数组要更新哦~
代码
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
/*求最大值索引，同时引用传递最大值*/
int maxIdx(vector<int> &arr, int &maxNum)
{
int len = arr.size();
int idx = 0;
maxNum = arr[idx];
for (int i = 1; i < len; ++i)
{
if (arr[i] >= maxNum )
{
maxNum = arr[i];
idx = i;
}//if
}//for
return idx;
}
/*计算小东还需要的票数*/
int count(vector<int> &arr)
{
int maxNum = 0,ret = 0;
int idx = maxIdx(arr, maxNum);
while (idx != 0)
{
--arr[idx];
++arr[0];
++ret;
idx = maxIdx(arr, maxNum);
}//while
return ret;
}
int main()
{
int n;
while (cin >> n)
{
vector<int> arr(n, 0);
for (int i = 0; i < n; ++i)
{
cin >> arr[i];
}//for
int ret = count(arr);
cout << ret << endl;
}
return 0;
}
编程2 -- 买糖果
题目
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem Description:
某糖果公司专门生产儿童糖果，它最受儿童欢迎的糖果有A1、A2两个序列，均采用盒式包装。包装好的A1类糖果体积为一个存储单位，而包装好的A2类糖果体积正好是A1类的两倍。
这两类糖果之所以广受儿童欢迎，是因为糖果中含有公司独家研发的魔幻因子。A1或A2序列中的糖果，看起来包装可能是一样的，但因为其中的魔幻因子含量不同被细分为不同的产品。
临近传统节日，公司的糖果供不应求。作为一个精明的糖果分销商，小东希望能够借此大赚一笔，于是带着现金开着货车来公司提货。货车的容量是确定的，小东希望采购的糖果能够尽可能装满货车，且糖果的魔幻因子总含量最高。只要不超出货车容量，糖果总可以装入货车中。
小东希望你能帮她解决这一问题。
输入
输入中有多组测试数据。每组测试数据的第一行有两个整数n和v，1<=n<=10^5, 1<=v<=10^9，n为可供选购糖果数量，v为货车的容量。随后n行为糖果的具体信息，第一行编号为1，第二行编号为2，以此类推，最后一行编号为n。每行包含两个整数ti和pi，1<=ti<=2, 1<=pi<=10^4，ti为糖果所属的序列，1为A1、2为A2，pi则是其中的魔幻因子含量。
输出
对每组测试数据，先在单独的一行中输出能采购的糖果中的魔幻因子最高含量，之后在单独的行中按编号从小到大的顺序输出以空格分隔的糖果编号，若有多组糖果组合均能满足要求，输出编号最小的组。若没有糖果能够满足要求，则在第一行中输出0，第二行输出“No”。
样例输入
3 2
1 2
2 7
1 3
样例输出
7
2
Problem Description:
某糖果公司专门生产儿童糖果，它最受儿童欢迎的糖果有A1、A2两个序列，均采用盒式包装。包装好的A1类糖果体积为一个存储单位，而包装好的A2类糖果体积正好是A1类的两倍。
这两类糖果之所以广受儿童欢迎，是因为糖果中含有公司独家研发的魔幻因子。A1或A2序列中的糖果，看起来包装可能是一样的，但因为其中的魔幻因子含量不同被细分为不同的产品。
临近传统节日，公司的糖果供不应求。作为一个精明的糖果分销商，小东希望能够借此大赚一笔，于是带着现金开着货车来公司提货。货车的容量是确定的，小东希望采购的糖果能够尽可能装满货车，且糖果的魔幻因子总含量最高。只要不超出货车容量，糖果总可以装入货车中。
小东希望你能帮她解决这一问题。
输入
输入中有多组测试数据。每组测试数据的第一行有两个整数n和v，1<=n<=10^5, 1<=v<=10^9，n为可供选购糖果数量，v为货车的容量。随后n行为糖果的具体信息，第一行编号为1，第二行编号为2，以此类推，最后一行编号为n。每行包含两个整数ti和pi，1<=ti<=2, 1<=pi<=10^4，ti为糖果所属的序列，1为A1、2为A2，pi则是其中的魔幻因子含量。
输出
对每组测试数据，先在单独的一行中输出能采购的糖果中的魔幻因子最高含量，之后在单独的行中按编号从小到大的顺序输出以空格分隔的糖果编号，若有多组糖果组合均能满足要求，输出编号最小的组。若没有糖果能够满足要求，则在第一行中输出0，第二行输出“No”。
样例输入
3 2
1 2
2 7
1 3
样例输出
7
2
分析
这道题是0-1背包的变形，注意多组结果时，保存序号小的那组。
代码
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
typedef struct Candy{
int t; /*糖果种类,也代表其体积*/
int p; /*糖果魔幻因子*/
Candy(int tt, int pp) :t(tt), p(pp){}
};
/*0-1背包解决*/
int maxValue(vector<Candy> &vc, vector<vector<int>> &path, int w)
{
if (vc.empty() || w <= 0)
return 0;
/*糖果的数量*/
int len = vc.size();
/*保存最大收益*/
vector<vector<int>> tmp(len + 1, vector<int>(w + 1, 0));
for (int i = 1; i <= len; ++i)
{
for (int j = 1; j <= w; ++j)
{
tmp[i][j] = tmp[i - 1][j];
path[i][j] = 0;
int weight = vc[i - 1].t, value = vc[i - 1].p;
/*注意收益值相等时保存序号小的那组*/
if (j >= weight && tmp[i][j] <= tmp[i - 1][j - weight] + value)
{
tmp[i][j] = tmp[i - 1][j - weight] + value;
path[i][j] = 1;
}//if
}//for
}//for
return tmp[len][w];
}
int main()
{
int n, w;
while (cin >> n >> w)
{
vector<Candy> cv;
for (int i = 0; i < n; ++i)
{
int t, p;
cin >> t >> p;
Candy c(t, p);
cv.push_back(c);
}//for
vector<vector<int>> path(n + 1, vector<int>(w + 1, 0));
vector<int> ret;
int maxRet = maxValue(cv, path, w);
if (maxRet == 0)
{
cout << 0 << endl;
cout << "No" << endl;
}
else{
cout << maxRet << endl;
bool start = true;
for (int i = n, j = w; i > 0 && j > 0;)
{
if (path[i][j] == 1)
{
ret.push_back(i);
j -= cv[i - 1].t;
}//if
--i;
}//for
/*打印结果*/
for (vector<int>::reverse_iterator iter = ret.rbegin(); iter != ret.rend(); ++iter)
{
if (start)
{
cout << *iter;
start = false;
}//if
else
{
cout << " " << *iter;
}//else
}//for
cout << endl;
}//else
}//while
return 0;
}