首页 > 其他分享 >CF1883E+CF1995C-对数+贪心

CF1883E+CF1995C-对数+贪心

时间:2024-08-02 16:18:32浏览次数:8  
标签:log int CF1995C long leq CF1883E 对数 贪心

CF1883E+CF1995C 对数+贪心

CF1883E Look Back

大致题意

给你一个整数数组$ a_1,a_2,…,a_n$ 。你需要用最少的运算次数使数组不递减。在一次操作中,您需要执行以下操作:

  • 选择一个索引 \(1 \leq i \leq n\) 、
  • 设置 $a_i = a_i⋅2 $.

数组 \(b_1,b_2,…,b_n\) 在所有$ 1 \leq i \leq n$ 都为$ b_i \leq b_{i+1}$ 的情况下是非递减的。

解法

我们可以看到数据范围是在\(a_1,a_2,…,a_n ( 1\leq a_i \leq 10^9 )\)的,所以我们如果直接去贪心的思考每次乘2是不行的(值会超过long long)

所以我们考虑将数值范围缩小,如果我们将数值取其对数,那么 $a_i = a_i⋅2 \(的操作则会转化为\)\log_2{(a_i*2)} == \log{a_i}+1$,那么此时则可以考虑贪心的方法

代码实现

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
const int N = 2e5+10;
void solve()
{
	int n;
	cin>>n;
	vector<int> a(n+1);
	vector<long double> b(n+1);
	for(int i = 1; i <= n;++i)
	{
		cin>>a[i];
		b[i] = log2l(a[i]);
	} 
	int ans = 0;
	for(int i = 2;i <= n;++i)
	{
		if(b[i]<b[i-1])
		{
			double d = b[i-1]-b[i];
			int c = (int)ceill(d);
			ans += c;
			b[i] += c;
		}
	}
	cout<<ans<<endl; 
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int tt;
	cin>>tt;
	while(tt--)solve();
	return 0;
} 

CF1995C-Squaring

大致题意

ikrpprpp 发现了一个由整数组成的数组 a 。他喜欢公平,所以想让 a 变得公平,也就是让它不递减。为此,他可以在数组的索引$ 1 \leq i \leq n $上执行一个公正的操作,将 \(a_i\) 替换为 \(a_i^2\) (位置 i 的元素及其平方)。例如,如果 $a=[2,4,3,3,5,3] $和ikrpprpp选择对 i=4 执行正义行动, a 就会变成 \([2,4,3,9,5,3]\) 。

要使数组不递减,最少需要多少次正义行动?

解法

思考的方向相同,我们依然不能直接使用贪心的思想,而是需要先收缩值域

我们对操作\(a_i=a_i^2\)的操作取对数得到\(\log{a_i} = 2\log{a_i}\) 此时我们将平方的操作转变为了每次乘2,但是依然有超出值域的风险,所以我们需要对其进行二次取对数

那么此时操作变为\(\log{\log{a_i}} = \log{\log{a_i}}+1\)

此时转为了加法操作且值域缩小,所以我们可以继续使用贪心的思想

代码实现

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
const int N = 2e5+10;
void solve()
{
	int n;
	cin>>n;
	vector<int> a(n+1);
	vector<long double> b(n+1);
	for(int i = 1;i <= n;++i)
	{
		cin>>a[i];
		int t = a[i];
		b[i] = log2l(log2l(t));
	} 
//	for(int i = 1;i <= n;++i) cout<<b[i]<<" \n"[i==n];
	long long ans = 0;
	for(int i = 2;i <= n;++i)
	{
		if(a[i] == 1&&i != 1&&a[i-1] != 1)
		{
			cout<<-1<<endl;
			return;
		}
		if(b[i]<b[i-1])
		{
			double c = b[i-1]-b[i];
			int res = (int)ceill(c);
			ans += res;
			b[i] += res;
		}
	}
//	for(int i = 1;i <= n;++i) cout<<b[i]<<" \n"[i==n];
	cout<<ans<<endl;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int tt;
	cin>>tt;
	while(tt--)solve();
	return 0;
} 

标签:log,int,CF1995C,long,leq,CF1883E,对数,贪心
From: https://www.cnblogs.com/empty-y/p/18338944

相关文章

  • 解密编程的八大法宝(三)(附贪心算法、动态规划和字符串匹配算法详解)
    算法题中常见的几大解题方法有以下几种:暴力枚举法(BruteForce):这是最基本的解题方法,直接尝试所有可能的组合或排列来找到答案。这种方法适用于问题规模较小的情况,但在大多数情况下效率不高。贪心算法(GreedyAlgorithm):贪心算法在每一步都选择当前看起来最优的解,希望最终能......
  • Day 31 贪心算法 Part05
    56.合并区间区间这类问题,不是按照左端点排序就是按照右端点排序,在思考思路的时候,就从这两个方向去下手,然后再去想贪心,以及从左侧开始遍历还是右侧开始遍历。classSolution{publicint[][]merge(int[][]intervals){if(intervals.length==1)returninterva......
  • 「代码随想录算法训练营」第二十六天 | 贪心算法 part4
    452.用最少数量的箭引爆气球题目链接:https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/题目难度:中等文章讲解:https://programmercarl.com/0452.用最少数量的箭引爆气球.html视频讲解:https://www.bilibili.com/video/BV1SA41167xe题目状态:有点思路......
  • 「代码随想录算法训练营」第二十五天 | 贪心算法 part3
    134.加油站题目链接:https://leetcode.cn/problems/gas-station/题目难度:中等文章讲解:https://programmercarl.com/0134.加油站.html视频讲解:https://www.bilibili.com/video/BV1jA411r7WX题目状态:没有思路,学习题解思路一:全局最优解首先将所有路径的加油量和耗油量加一起......
  • 洛谷P3161 [CQOI2012] 模拟工厂 贪心策略的思考
    P3161[CQOI2012]模拟工厂传送门:模拟工厂问题描述:初始的生产力和商品分别为1和0。每一个时刻可以选择两个动作:生产力+1或者生产生产力数量的商品。现在有很多个订单,每个订单有三个部分:时间t,需要多少商品p,可以获得的价值v。现在需要决定各个时刻的动作选择,以及订单是否接取,以期......
  • Day 30 贪心算法 Part04
    452.用最少数量的箭引爆气球自己写没写出来,不过找到篇很好的题解,贪心想不到就是想不到,没办法。本以为自己的思路也是贪心,但就是做不出来。classSolution{publicintfindMinArrowShots(int[][]points){boolean[]visited=newboolean[points.length];......
  • LeetCode 3111. 覆盖所有点的最少矩形数目(贪心、排序)
    题目:3111.覆盖所有点的最少矩形数目思路:只需关注横坐标,对横坐标进行升序排序,然后进行贪心,求得最少的矩阵数量classSolution{public:intminRectanglesToCoverPoints(vector<vector<int>>&points,intw){vector<int>v;for(inti=0;i<poi......
  • CF1995C Squaring 题解
    思路详解:请注意,本题解用到了非整数计算,也就是说性能可能不如整数运算,但是易于实现,追求最优解的大佬不建议观看本题解。这个题看似简单,但是由于涉及到了平方操作,不用高精度根本存不下,然后如果你要用高精度的话又会T......
  • Day 29 贪心算法 Part03
    今天的题目真是给我做恶心了134.加油站暴力方法很容易写出来,但在力扣上运行会超时。classSolution{int[]gas;int[]cost;publicintcanCompleteCircuit(int[]gas,int[]cost){this.gas=gas;this.cost=cost;for(inti=......
  • (nice!!!)LeetCode 2952. 需要添加的硬币的最小数量(贪心、数组)
    题目:2952.需要添加的硬币的最小数量思路:假设区间[1,s-1]的数都可组合得到,当遍历到x=coins[i]时,1、当x<=s时,可以组合的数就是区间[1,s-1]和区间[x,s-1+x]的交集,即区间[1,s-1+x]2、当x>s时,区间[1,s-1]和区间[x,s-1+x]没有交集,那我就只能通过添加一个数来实现了。在这里......