第三次算法集训

第三次算法集训

目录

A 排队接水B kkksc03考前临时抱佛脚C 约瑟夫问题D 选数

---

A 排队接水

链接：https://www.luogu.com.cn/problem/P1223
标签：贪心
题解：将接水时间从小到大排序，然后计算总等待时间，ans 指单个人要等待的时间，sum 指所有人要等待的时间。

#include
using namespace std;
const int N = 1e3 + 10;
pair a[N];
int main() {
	int n;
	cin>> n;
	for(int i = 1; i <= n; i ++) {
		cin >> a[i].first;
		a[i].second = i;
	}
	sort(a+1, a+n+1);
	double ans = 0,sum = 0;//不能用int
	for(int i = 1; i <= n; i ++) {
		sum += ans;
		ans += a[i].first;		
	}
	for(int i = 1; i <= n; i ++) cout<< a[i].second <<" ";
	printf("n%.2fn",sum / n);
	return 0;
}

B kkksc03考前临时抱佛脚

链接：https://www.luogu.com.cn/problem/P2392
标签：动态规划，01背包（注：会误认为这题是贪心）
题解：将数据划分成两个部分，然后取两边的最大值。即转化为判断其中一部分最大接近和ans / 2。

#include
using namespace std;
int a[5],b[25];
int check(int n) {
	int ans = 0;
	for(int i = 1; i <= n; i ++) {
		cin>> b[i];
		ans += b[i];
	}
	int dp[25][1250] = {0}, cnt = ans / 2;
	//dp[i][j]指前i件物品，共有容量j，可以最大装下dp[i][j]的容量
	// 01 背包 ，目的：求dp[cnt] max
	for(int i = 1; i <= n; i ++) {
		for(int j = 0; j <= cnt; j ++) {
			dp[i][j] = dp[i-1][j]; // 不可以装下 
			if(j >= b[i]) dp[i][j] = max(dp[i][j],dp[i-1][j - b[i] ] + b[i]); // 可以装下
		}
	}
	return ans - dp[n][cnt]; 
}
int main() {
	int sum = 0;
	for(int i = 0; i < 4; i ++) cin>> a[i];
	for(int i = 0; i < 4; i ++) {
		sum += check(a[i]);
	}
	cout<< sum << endl;
	return 0;
}

C 约瑟夫问题

链接：https://www.luogu.com.cn/problem/P1996
标签：暴力，（可以用队列，链表等知识）
题解：暴力循环，出圈的同学被标记

#include
using namespace std;
int a[105];
int main() {
	int n,m, t = 0, k = 0;
	cin>> n >> m;
	for(int i = 1; i <= n; i ++) a[i] = i;
	int i = 1;
	while(1) {
		if(a[i] != -1) {
			t ++;
			if( t == m) {
				cout<< a[i] << " ";
				a[i] = -1;
				t = 0;
				k ++;
			}			
		}
		i ++;
		if( k == n) break;
		if( i == n + 1) i = 1;
	}
	return 0;
}

其他约瑟夫问题：https://blog.csdn.net/a_forever_dream/article/details/100769164

D 选数

链接：https://www.luogu.com.cn/problem/P1036
标签：搜索，素数
题解：两种选择：1选择第 i 个数，2不选择第 i 个数。深搜即可，注意退出条件。

#include
using namespace std;
int a[25],b[25];
int n,m, cnt ;
bool isprime(int n) { // 素数
	if( n <= 1 ) return false;
	for(int i = 2; i <= n / i; i ++)
	if(n % i == 0) return false;
	return true;
}
void dfs(int step,int k,int ans) {// step 指到了第 step 个数，k 选择了 k 个数
	if(k >= m ) {
		if(isprime(ans)) cnt ++;
		return ;
	}
	if(step >= n) return ;
	dfs(step + 1, k + 1, ans + a[step]); // 选择第step个数
	dfs(step + 1, k, ans);// 不选择第step个数
}
int main() {  
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
    	cin >> a[i];
	}
	dfs(0,0,0);
	cout << cnt << endl;
    return 0;
}