首页 > 代码库 > Codeforces 712C Memory and De-Evolution（逆向思维）
Codeforces 712C Memory and De-Evolution（逆向思维）
题目链接：http://codeforces.com/problemset/problem/712/C
题意：有一个长度为 x 的等边三角形，你每次可以选择一条边减少其长度，当然减少之后，三条边仍然可以组成一个三角形。
最后要使其变成程度为 y ，的等边三角形（x > y），问要作几次操作。
思路：贪心即可，可是重点是反着贪，长度为 y 的等边三角形，每次增加一条边的长度使其变成长度为 x 的等边三角形。
如果正着贪心，一条边太短的话，很影响其他边变短的过程，总次数也不一定是最优。
代码：
#include <iostream>#include <stdio.h>#include <cstring>#include <queue>#include <set>#include <cmath>#include <algorithm>using namespace std;const int N = 100007;const int INF = (int)1e9 + 100;const int MOD = (int)1e9 + 7;int main(){ int x, y; while (scanf("%d%d", &x, &y) != EOF) { int v[4]; v[1] = y, v[2] = y, v[3] = y; int cnt = 0; while (v[1] != x || v[2] != x || v[3] != x) { sort(v + 1, v + 4); int dif = v[3] + v[2] - 1; v[1] = dif > x ? x : dif; cnt++; //printf("%d %d %d\n", v[1], v[2], v[3]); } printf("%d\n", cnt); }}
Codeforces 712C Memory and De-Evolution（逆向思维）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。