Code – 第227页

蓝桥杯 ALGO-34 算法训练纪念品分组（贪心算法+排序）

问题描述
　　元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。
　　你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。
输入格式
　　输入包含n+2行：
　　第1行包括一个整数w，为每组纪念品价格之和的上限。
　　第2行为一个整数n，表示购来的纪念品的总件数。
　　第3~n+2行每行包含一个正整数pi (5 <= pi <= w)，表示所对应纪念品的价格。
输出格式
　　输出仅一行，包含一个整数，即最少的分组数目。
样例输入
100
9
90
20
20
30
50
60
70
80
90
样例输出
6
数据规模和约定
　　50%的数据满足：1 <= n <= 15
　　100%的数据满足：1 <= n <= 30000, 80 <= w <= 200
分析：排序+贪心。先从小到大排序，i、j指针分别从左到右、从右到左遍历。
如果a[i]+a[j] <= w，那么把这两个物品都放入同一组，并且同时移动指针；
否则，只能把j所指向的物品放入单独的一个组，移动j指针…直到i j把所有物品都遍历完~

分析下贪心算法的可行性：如果j物品和i物品加起来超过了w，因为j物品比j+1处的物品价值小，那么如果i不能满足加起来的条件，而i-1能满足该条件，是否会影响贪心算法的结果呢？
如果让j和i-1去组合，对于j+1，因为价值比j更大，所以就更放不进i了，所以即使交换组合方式还是不影响构成的组数的~

至于为什么循环的条件是i <= j，当i<j的时候，假设i j已经相邻，那么此时还能再比较一次i+j能否满足构成一组的条件，如果满足就会把它们放到一组，之后i j指针同时移动后i>j不能够满足进入循环的条件了；如果不满足把它们放入一组，那么j放入一组后j移动指针，使i == j，继续进入循环；
当i == j的时候，因为这个单独的物品已经没有可以组合的物品剩余了，所以此时还要进入循环进行一次 cnt++ 的计数操作~//这就是while(i <= j)的解释~~~

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int main() {
	int w, n;
	scanf("%d %d", &w, &n);
	int *a = new int[n];
	for(int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	sort(a, a+n);
	int i = 0, j = n-1, cnt = 0;
	while(i <= j) {
		if(a[i] + a[j] <= w) {
			i++;
		}
		cnt++;
		j--;
	}
	cout << cnt;
	return 0;
}

#include <iostream>

#include <algorithm>

#include <cstdio>

using namespace std;

int main() {

int w, n;

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

int *a = new int[n];

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

scanf("%d", &a[i]);

sort(a, a+n);

int i = 0, j = n-1, cnt = 0;

while(i <= j) {

if(a[i] + a[j] <= w) {

i++;

}

cnt++;

j--;

}

cout << cnt;

return 0;

}

蓝桥杯 ALGO-2 算法训练最大最小公倍数（贪心算法）

问题描述
已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。

输入格式
输入一个正整数N。

输出格式
输出一个整数，表示你找到的最小公倍数。
样例输入
9
样例输出
504
数据规模与约定
1 <= N <= 10^6。

分析:
1.如果 n <= 2, 那么最小公倍数为 n
2.如果 n 是奇数，那么最小公倍数的最大值为末尾的三个数相乘
3.如果是偶数的话，如果同时出现两个偶数肯定会不能构成最大值了，因为会被除以2~~分两种情况：
(1)如果 n 是偶数且不是三的倍数，比如8，那么跳过n-2这个数而选择 8 7 5 能保证不会最小公倍数被除以2~~所以最小公倍数的最大值为n * (n – 1) * (n – 3)
(2)如果 n 是偶数且为三的倍数，比如6，如果还像上面那样选择的话，6和3相差3会被约去一个3，又不能构成最大值了。那么最小公倍数的最大值为(n – 1) * (n – 2) * (n – 3)

#include <iostream>  
using namespace std;  
int main() {  
    long long n, ans;  
    cin >> n;  
    if(n <= 2)  
        ans = n;  
    else if(n % 2 == 1)  
        ans = n * (n-1) * (n-2);  
    else if(n % 3 == 0)  
        ans = (n - 1) * (n - 2) * (n - 3);  
    else  
        ans = n * (n - 1) * (n - 3);    
    cout << ans;  
    return 0;  
}

#include <iostream>

using namespace std;

int main() {

long long n, ans;

cin >> n;

if(n <= 2)

ans = n;

else if(n % 2 == 1)

ans = n * (n-1) * (n-2);

else if(n % 3 == 0)

ans = (n - 1) * (n - 2) * (n - 3);

else

ans = n * (n - 1) * (n - 3);

cout << ans;

return 0;

}

蓝桥杯 PREV-5 历届试题错误票据

问题描述
某涉密单位下发了某种票据，并要在年终全部收回。
每张票据有唯一的ID号。全年所有票据的ID号是连续的，但ID的开始数码是随机选定的。
因为工作人员疏忽，在录入ID号的时候发生了一处错误，造成了某个ID断号，另外一个ID重号。
你的任务是通过编程，找出断号的ID和重号的ID。
假设断号不可能发生在最大和最小号。
输入格式
要求程序首先输入一个整数N(N<100)表示后面数据行数。
接着读入N行数据。
每行数据长度不等，是用空格分开的若干个（不大于100个）正整数（不大于100000），请注意行内和行末可能有多余的空格，你的程序需要能处理这些空格。
每个整数代表一个ID号。
输出格式
要求程序输出1行，含两个整数m n，用空格分隔。
其中，m表示断号ID，n表示重号ID

样例输入1
2
5 6 8 11 9
10 12 9
样例输出1
7 9
样例输入2
6
164 178 108 109 180 155 141 159 104 182 179 118 137 184 115 124 125 129 168 196
172 189 127 107 112 192 103 131 133 169 158
128 102 110 148 139 157 140 195 197
185 152 135 106 123 173 122 136 174 191 145 116 151 143 175 120 161 134 162 190
149 138 142 146 199 126 165 156 153 193 144 166 170 121 171 132 101 194 187 188
113 130 176 154 177 120 117 150 114 183 186 181 100 163 160 167 147 198 111 119
样例输出2
105 120

分析：把它们一个个放到集合里面，要是集合的容量不变说明是重复的数字~然后遍历集合，如果集合有一个数字不连续那就是这个数字是错误的~
用了while(cin >> a)后，发现第一个变量给不给都一样。。反正没什么用。。

#include <iostream>
#include <set>
using namespace std;
int main() {
    set<int> s;
    int row, a, m = 0, n = 0, size;
    cin >> row;
    while(cin >> a) {
        size = s.size();
        s.insert(a);
        if(s.size() == size) {
            n = a;
        }
    }
    set<int>::iterator it = s.begin();
    set<int>::iterator itt = it;
    for(it++ ; it != s.end(); it++, itt++) {
        
        if(*it != *itt + 1) {
            m = *itt + 1;
        }
    }
    cout << m << " " << n;
    return 0;
}

#include <iostream>

#include <set>

using namespace std;

int main() {

set<int> s;

int row, a, m = 0, n = 0, size;

cin >> row;

while(cin >> a) {

size = s.size();

s.insert(a);

if(s.size() == size) {

n = a;

}

set<int>::iterator it = s.begin();

set<int>::iterator itt = it;

for(it++ ; it != s.end(); it++, itt++) {

if(*it != *itt + 1) {

m = *itt + 1;

}

cout << m << " " << n;

return 0;

}

蓝桥杯 ADV-144 算法提高 01背包

问题描述
　　给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个.
输入格式
　　输入的第一行包含两个整数n, m，分别表示物品的个数和背包能装重量。
　　以后N行每行两个数Wi和Vi,表示物品的重量和价值
输出格式
　　输出1行，包含一个整数，表示最大价值。
样例输入
3 5
2 3
3 5
4 7
样例输出
8
数据规模和约定
　　1<=N<=200,M<=5000.

分析：dp[i][j]表示前i件物品选择部分装入体积为j的背包后，背包当前的最大价值，
一共有n件物品，那么dp[n][m]就是前n件物品选择部分装入容量为m的背包后，背包内物品的最大价值
1.当当前输入的物品体积大于背包容量，则不装入背包，dp[i][j] = dp[i-1][j];
2.当当前输入的物品体积小于等于背包容量，考虑装或者不装两种状态，取体积最大的那个：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v);

#include <iostream>
using namespace std;
int dp[201][5001];
int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        int w, v;
        cin >> w >> v;
        for(int j = 1; j <= m; j++) {
            if (j >= w)
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v);
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    cout << dp[n][m];
    return 0;
}

#include <iostream>

using namespace std;

int dp[201][5001];

int main() {

int n, m;

cin >> n >> m;

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

int w, v;

cin >> w >> v;

for(int j = 1; j <= m; j++) {

if (j >= w)

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v);

else

dp[i][j] = dp[i-1][j];

}

cout << dp[n][m];

return 0;

}

蓝桥杯 ALGO-30 算法训练入学考试（01背包，动态规划）

问题描述
　　辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
　　如果你是辰辰，你能完成这个任务吗？
输入格式
　　第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。
输出格式
　　包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
样例输入
70 3
71 100
69 1
1 2
样例输出
3
数据规模和约定
　　对于30%的数据，M <= 10；
　　对于全部的数据，M <= 100。

分析：01背包问题。对于每一个输入都有采和不采两种状态。
dp[i][j]表示对于前i个草药选择部分采且总时间不超过j小时后，草药的价值的最大值
可得dp[M][T]即是所求的解。
1.当当前输入的草药所需时间大于允许的最大时间j小时的时候，则不采，dp[i][j] = dp[i-1][j];
2.当当前输入的草药所需时间小于等于允许的最大时间小时的时候，考虑采或者不采两种状态，取能够使草药总价值最大的那个：dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + b);

#include <iostream>
using namespace std;
int dp[101][1001];
int main() {
    int t, m;
    cin >> t >> m;
    for(int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        for(int j = 1; j <= t; j++) {
            if(j >= a)
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + b);
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    cout << dp[m][t];
    return 0;
}

#include <iostream>

using namespace std;

int dp[101][1001];

int main() {

int t, m;

cin >> t >> m;

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

int a, b;

cin >> a >> b;

for(int j = 1; j <= t; j++) {

if(j >= a)

dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + b);

else

dp[i][j] = dp[i-1][j];

}

cout << dp[m][t];

return 0;

}

蓝桥杯 ALGO-31 算法训练开心的金明（01背包，动态规划）

问题描述
　　金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：
“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，
肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
　　设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为 j1，j2，……，jk，则所求的总和为：
　　v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。（其中*为乘号）
　　请你帮助金明设计一个满足要求的购物单。
输入格式
　　输入文件的第1行，为两个正整数，用一个空格隔开：
　　N m
　　（其中N（<30000）表示总钱数，m（<25）为希望购买物品的个数。）
　　从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数
　　v p
　　（其中v表示该物品的价格(v<=10000)，p表示该物品的重要度(1~5)）
输出格式
　　输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<100000000）。
样例输入
1000 5
800 2
400 5
300 5
400 3
200 2
样例输出
3900
分析：01背包问题。对于每一个输入都有买和不买两种状态。
dp[i][j]表示对于前i件物品选择部分购买限定总价不超过j元后，物品的价格与重要程度乘积的总和的最大值
可得dp[m][n]即是所求的解。
1.当当前输入的物品价格大于允许的最大总价j元，则不买，dp[i][j] = dp[i-1][j];
2.当当前输入的物品体积小于等于允许的最大总价j元，考虑买或者不买两种状态，取物品的价格与重要程度乘积的总和最大的那个：dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + t);

#include <iostream>
using namespace std;
int dp[25][30000];
int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        for(int j = 1; j <= n; j++) {
            if(j >= a)
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + a * b);
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    cout << dp[m][n];
    return 0;
}

#include <iostream>

using namespace std;

int dp[25][30000];

int main() {

int n, m;

cin >> n >> m;

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

int a, b;

cin >> a >> b;

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

if(j >= a)

dp[i][j] = max(dp[i-1][j], dp[i-1][j-a] + a * b);

else

dp[i][j] = dp[i-1][j];

}

cout << dp[m][n];

return 0;

}