每日算法 - day 30

每日算法

those times when you get up early and you work hard; those times when you stay up late and you work hard; those times when don’t feel like working — you’re too tired, you don’t want to push yourself — but you do it anyway. That is actually the dream. That’s the dream. It’s not the destination, it’s the journey. And if you guys can understand that, what you’ll see happen is that you won’t accomplish your dreams, your dreams won’t come true, something greater will. mamba out

那些你早出晚归付出的刻苦努力，你不想训练，当你觉的太累了但还是要咬牙坚持的时候，那就是在追逐梦想，不要在意终点有什么，要享受路途的过程，或许你不能成就梦想，但一定会有更伟大的事情随之而来。 mamba out~

2020.3.16

luogu -P1190 接水问题

按照题意模拟即可

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace  std;
const int N = 10005;

int a[N] , n , m  ,sum = 0;
int main()
{
	cin >> n >> m;	
	for(int i = 0;i < n ;i ++)
	{
		cin >> a[i];
		sum += a[i];
	} 
	
	int waitman = m,time = 0; //m排队 
	while(sum)
	{
		for(int i = 0;i < m ;i ++)
		{	
			if(a[i] > 0){
				a[i]--;sum--;
			}
			if(a[i] == 0){ //接满换人 
				a[i] = a[waitman++];
				if(waitman >= n)waitman = n;
			}
		}
		time++;
	}
	cout << time << endl;
	return 0;	
} 

P1109 学生分组

贪心 + 模拟
优先让其取到边界值，如果他多出来就让它分到其他组，如果少了就把其他组员的成员且没有到最低限度的给拿出来

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>

using namespace std;
const int N = 100;

int a[N] , n , l ,r , sum = 0;
int s, b;
int main()
{
	
	cin >> n;
	for(int i = 0; i < n ;i ++)
	{
		cin >> a[i];
	}
	cin >> l >> r;
	
	for(int i = 0; i < n ;i ++)
	{
		if(a[i] < l){
			s = s - (l - a[i]);
			a[i] = l;
		}
		if(a[i] > r){
			b = b + (a[i] - r);
			a[i] = r;
		}
	}
	
	if(b + s > 0)sum += -s;
	else sum += b;
	
	sort(a, a + n);

	int t = s + b;
	if(t == 0){
		cout << sum << endl;return 0;
	}
	
	for(int i = 0;i < n ;i ++)
	{
		if(t < 0) // 如果left < 0 意味着我需要从其他位置去借人 
		{
			if(a[i] > l)
			{
				int brown = a[i] - l;
				if(t + brown >= 0){
					t = 0;break;
				}else t = t + brown;
			}
		}else{  // 如果left > 0意味着我需要去哪些还没满的位置上增加人 
			if(a[i] < r)
			{
				int add = r - a[i];
				if(t - add <= 0){
					t = 0;break;
				}else t = t - add;
			}
		}
	}
	if(t == 0)cout << sum + abs(s + b) << endl;
	else cout << -1 << endl;
	return 0;
}

P1244 [NOI2000]青蛙过河

dp的思路 先将问题分解为子问题 ，从最初的状态开始考虑。往后依次推出之后的状态

f[k][h] 表示有 K 个荷叶 h个石头的方法
f[0][0] = 1
f[1][0] = 2;
f[2][0] = 3;
...
f[k][0] = k + 1;

而我们石头的和荷叶都存在时候
f[0][0] = 1 f[0][1] = 2 f[0][2] = 4
f[k][h] = f[k][h-1] * 2;

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>


/*
当无石头时，能通过的青蛙数量为k+1只
之后，随着石头数量的增加，方法数ans*2
*/
using namespace std;
int h , k , ans = 0;
int main()
{
	
	cin >> h >> k;
	ans = k + 1;
	
	for(int i = 1;i <= h ;i ++)
	{
		ans = ans * 2;
	}
	
	cout << ans << endl;
	return 0;
}

P1184 高手之在一起

水题 早知道这么水就不做了 hh

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <map>
using namespace std;


int n , m ,ans = 0;

map<string,bool> v;

int main()
{
	cin >> n >> m;
	getchar();
	string s , a;
	for(int i = 0;i < n ;i ++)
	{
		cin >> s;
		while(getchar() == ' ')
		{
			cin >> a;s+=a;
		}
		v[s] = 1;
		
	}
	for(int i = 0;i < m ;i ++)
	{
		cin >> s;
		while(getchar() == ' ')
		{
			cin >> a;s+=a;
		}
		if(v[s])ans++;
	}
	
	cout << ans << endl;
	return 0;
}