Daliy Algorithm (heap，greedy , IQ )-- day 91

2024-03-16 16:14:40

Nothing to fear

种一棵树最好的时间是十年前，其次是现在！

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

2020.6.30

人一我十，人十我百，追逐青春的梦想，怀着自信的心，永不言弃！

Pluses and Minuses

思路：

利用前缀和思想，我们把加号和减号所组成的字符串改为+ ： 1， - ： -1。因此我们可以得到一个前缀和序列。此时遍历字符串s，如果当前位置的前缀和比上一次最大的前缀和要小，那么即对应于题目种的cur < 0此时需要累加结果并将当前标准替换.

注意初始化的时候res = len(s) ，因为原题目中退出循环的条件是s全部遍历完毕中间不会出现停止。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <cassert>
#include <string>
#include <iomanip>
#include <cmath>
#include <ctime>
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
using namespace std;
typedef long long ll;
const int MAX = 0x7ffffff;
int t;

void slove()
{
	string s;
	cin >> s;
	ll cur = 0 , res = s.size() , mn = 0;
	for(int i = 0;i < s.size();i ++)
	{
		cur += (s[i] == '+' ? 1 : -1);
		if(cur < mn)
		{
			mn = cur;
			res += i + 1;
		}
	}
	cout << res << endl;
}
int main()
{
#ifdef LOCAL
	auto start_time = clock();
	cerr << setprecision(3) << fixed; // 在iomanip中
#endif
	SIS;
	cin >> t;
	while(t--)
	{
		slove();
	}
#ifdef LOCAL
	auto end_time = clock();
	cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
}

AccurateLee

分析

  1. 首先应该检查是否存在单调递减的相邻的子序列，如果存在则需要进行消除处理，如果不存在则无需处理直接输出原来的内容即可

  2. 通过观察我们发现在字符串中最后一个0之前的1都会被消除掉，而第一个1之前的0则无法被消除，故我们需要保留第一个1之前的所有0，和最后一个0之后的所有1就是答案。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <cassert>
#include <string>
#include <iomanip>
#include <cmath>
#include <ctime>
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
#define sn string::npos
using namespace std;
typedef long long ll;
const int MAX = 0x7ffffff;
int t;

void slove()
{
	int n , flag = 0;
	string s;
	cin >> n >> s;
	for(int i = 1;i < s.size();i ++)
	{
		if(s[i] < s[i - 1])flag = 1;
	}
	if(!flag){
		cout << s << endl;
		return;
	}
	string ans;
	for(int i = 0;i < s.size();i ++)
	{
		if(s[i] == '1')break;
		ans += "0";
	}
	ans += "0";
	for(int i = s.size() - 1;i >= 0;i--)
	{
		if(s[i] == '0')break;
		ans += "1";
	}
	cout << ans << endl;
	return;
}
int main()
{
#ifdef LOCAL
	auto start_time = clock();
	cerr << setprecision(3) << fixed; // 在iomanip中
#endif
	SIS;
	cin >> t;
	while(t--)
	{
		slove();
	}
#ifdef LOCAL
	auto end_time = clock();
	cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
}

RationalLee

分析

贪心 + 排序

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <cassert>
#include <string>
#include <iomanip>
#include <cmath>
#include <ctime>
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
using namespace std;
typedef long long ll;
const int MAX = 0x7ffffff;
int t;

void slove()
{
	int n , k;
	cin >> n >> k;
	vector<int> a(n) , w(k);
	for(int i = 0;i < n;i ++)cin >> a[i];
	for(int i = 0;i < k;i ++)cin >> w[i];
	sort(a.begin(),a.end());
	sort(w.begin(),w.end());
	int l = n - 1 - k,r = n - 1;
	ll ans = 0;
	for(int i = 0;i < k;i++)
	{
		int c = w[i];
		int maxc = a[r] , minc = a[r];
		r--;
		if(c > 1)
		{
			int id = 0;
			while(id < (w[i] - 1))
			{
				id++;
				minc = min(minc , a[l--]);
			}
		}
		//printf("max = %d min = %d\n",maxc , minc);
		ans = ans + maxc + minc;
	}
	cout << ans << endl;
}
int main()
{
#ifdef LOCAL
	auto start_time = clock();
	cerr << setprecision(3) << fixed; // 在iomanip中
#endif
	SIS;
	cin >> t;
	while(t--)
	{
		slove();
	}
#ifdef LOCAL
	auto end_time = clock();
	cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
}

GPLT-L2-012关于堆的判断

分析

根据题意我们需要简历一个小顶堆来进行判断操作

  • 1.判断是否是根节点只需要判断heap[1] == x;
  • 2.判断是否是兄弟结点需要判断 [x , x + 1] 或者 [x , x -1],根据x的所在堆数组中的位置进行判断。
  • 3.判断是否为父节点：假设x在heap数组中的索引为 I ，那么只需要判断 H[i * 2] 和 H[i * 2 + 1] 是否存在 y 即可
  • 4.判断子节点只需要将第三点反过来即可
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;
#define npos string::npos
const int N = 1005;

int n , m;
int a[N] , H[N] ,size = 0;
bool ans[N];int len;
void up(int p)
{
	while(p > 1)
	{
		if(H[p] < H[p / 2]){
			swap(H[p] , H[p / 2]);
			p /= 2;
		}else break;
	}
}
void insert(int x)
{
	H[++size] = x;
	up(size);
}
void checkroot(string s)
{
	string root;
	int id = s.find("is");
	root = s.substr(0,id - 1);
	int num = stoi(root);
	if(num == H[1])ans[len++] = 1;
	else ans[len++] = 0;
}	
void checksibling(string s)
{
	string a , b;
	int x = s.find("and") , y = s.find("are");
	a = s.substr(0,x-1);
	b = s.substr(x + 4,(y - 1 - x - 4));
	int c = stoi(a) , d = stoi(b);
	for(int i = 1;i <= n;i++)
	{
		if(H[i] == c || H[i] == d)
		{
			if(i % 2 == 0){
				if((H[i] + H[i + 1]) == c + d)ans[len++] = 1;
				else ans[len++] = 0;
			}else {
				if((H[i] + H[i - 1]) == c + d)ans[len++] = 1;
				else ans[len++] = 0;
			}
			return;
		}
	}
}
void checkparent(string s)
{
	string a , b;
	int x = s.find("is"),y = s.find("of");
	a = s.substr(0,x-1);
	b = s.substr(y+3,s.size() - y - 3);
	int c = stoi(a) , d = stoi(b);
	for(int i = 1;i <= n;i++)
	{
		if(H[i] == c)
		{
			if(H[i * 2] == d || H[i * 2 + 1] == d)ans[len++] = 1;
			else ans[len++] = 0;
		}
	}
}
void checkchild(string s)
{
	string a , b;
	int x = s.find("is"),y = s.find("of");
	a = s.substr(0,x-1);
	b = s.substr(y+3,s.size() - y - 3);
	int c = stoi(a) , d = stoi(b);
	for(int i = 1;i <= n;i++)
	{
		if(H[i] == d)
		{
			if(H[i * 2] == c || H[i * 2 + 1] == c)ans[len++] = 1;
			else ans[len++] = 0;
		}
	}
}
void query(string s)
{
	if(s.find("root") != npos)checkroot(s);
	if(s.find("siblings") != npos)checksibling(s);
	if(s.find("parent") != npos)checkparent(s);
	if(s.find("child") != npos)checkchild(s);
}	
void input()
{
	cin >> n >> m;
	for(int i = 1;i <= n;i ++){
		scanf("%d",&a[i]);
		insert(a[i]);
	}getchar();	
	string q;
	for(int i = 0;i < m;i ++)
	{
		getline(cin , q);query(q);
	}
}
int main()
{
	input();
	for(int i = 0;i < len;i ++)
	{
		printf("%s\n",(ans[i] == 1 ? "T" : "F"));
	}
	return 0;
}
上一篇：Daliy Algorithm (字符串，暴力，数学)-- day 96


下一篇：Algorithm算法库