✨✨ 欢迎大家来访Srlua的博文(づ ̄3 ̄)づ╭❤~✨✨ 🌟🌟 欢迎各位亲爱的读者,感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢,在这里我会分享我的知识和经验。🎥 希望在这里,我们能一起探索IT世界的奥妙,提升我们的技能。🔮 记得先点赞👍后阅读哦~ 👏👏
构造法没有明显决策过程,只是把决策放到了推导阶段,灵活性高,大多数刚接触贪心算法的人不知道如何下手
思路1:拆成尽可能多的2,因为当a,b>2时,a x b > a + b
问题:需要拆成“不同的”数字,2只能出现一次
思路2:拆成尽可能小的数字,比如9 = 2 + 3 + 4,就好过9 = 5 + 4,因为2 x 3 > 2 + 3
问题:10=2+3+4+...1? 余1怎么办?
1补到4上变成5,10=2+3+5 是最优拆分
why?
如果把10改为12呢 ?
12=2+3+4+...3
把3都分配给4,变成2+3+7,2x3x7=42不是最优,
例:2+4+6,2x4x6=48
最优方案:最后三个数各加1,3x4x5=60
越趋向平均越好,比如给2x4分配1,那么3x4>2x5
由于数字必须不同,不保证能从第一个数开始加。
例:2+3+4如果把1加给2,变成3+3+4,则两个3冲突。
除非——余数足够大,可以分给下一个数,下下一个数......直到最后一个数
1.将N拆分成2+3+4+...+(M-1)+M+K(余数)的形式0≤K≤M
2.从M开始向前倒推K个数,给每个数字都加1,变成2+3+...+(M-K-1)+(M-K+1)+(M-K+2)+...+M+(M+1)。
特例:K=M时,最后一个数是M+2
3.可以证明该拆分为最优~
#include<bits/stdc++.h>
using namespace std;
const int MAX_RAND_TIME = 1000000;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
cin >> n >> m;
int a[n];
double avg = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
avg += a[i];
}
avg /= m;
double res = INT_MAX;
for (int times = 0; times < MAX_RAND_TIME; times++) {
random_shuffle(a, a + n);
int sum[m];
memset(sum, 0, sizeof(sum));
for (int i = 0; i < n; i++) {
int min_j = 0;
for (int j = 1; j < m; j++)
if (sum[j] < sum[min_j])
min_j = j;
sum[min_j] += a[i];
}
double s = 0;
for (int i = 0; i < m; i++)
s += (avg - sum[i]) * (avg - sum[i]);
s = sqrt(s / m);
res = min(res, s);
}
cout << fixed << setprecision(2) << res << endl;
return 0;
}
1.通常有一个比较直观,容易想到或者计算出来的“规律“
2.边界条件经常需要特殊判断和处理
3.决策过程隐含在规律和边界条件中
最多只能恢复8点能量+闪1次
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, s;
cin >> n >> s;
int p, y, min_p = INT_MAX - s;
long long total = 0;
for (int i = 0; i < n; i++) {
cin >> p >> y;
min_p += s;
if (min_p > p)
min_p = p;
total += min_p * y;
}
cout << total << endl;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
int a[n + 1], count[4];
memset(count, 0, sizeof(count));
for (int i = 1; i <= n; i++) {
cin >> a[i];
count[a[i]] ++;
}
int res = 0;
int j2 = count[1] + 1, j3 = count[1] + count[2] + 1;
for (int i = 1; i <= count[1]; i++) {
if (a[i] == 2) {
while (j2 <= count[1] + count[2] && a[j2] != 1)
j2 ++;
if (j2 <= count[1] + count[2]) {
int tmp = a[i]; a[i] = a[j2]; a[j2] = tmp;
res ++;
}
} else if (a[i] == 3) {
while (j3 <= n && a[j3] != 1)
j3 ++;
if (j3 <= n) {
int tmp = a[i]; a[i] = a[j3]; a[j3] = tmp;
res ++;
}
}
}
int j = count[1] + 1;
for (int i = 1; i <= count[1]; i++) {
if (a[i] != 1) {
while (j <= n && a[j] != 1)
j ++;
if (j <= n) {
int tmp = a[i]; a[i] = a[j]; a[j] = tmp;
res ++;
}
}
}
for (int i = count[1] + 1; i <= count[1] + count[2]; i++)
if (a[i] == 3)
res ++;
cout << res << endl;
return 0;
}
1.找出一种从起始状态转移到目标状态的方法,这个方法不一定是最优,但一定要是可行并且套路化的方法
2.挖掘出这个转移方法的额外步骤/代价
3.通过一定的规则,去掉这个额外的步骤和代价
希望对你有帮助!加油!
若您认为本文内容有益,请不吝赐予赞同并订阅,以便持续接收有价值的信息。衷心感谢您的关注和支持!