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