P2660 zzc 种田

P2660 zzc 种田

核心思路：我们发现我们每次最好是尽量切除最大的正方形，因为这样子我们可以尽量避免同一个位置的边被切多次（达到贪心的思想）：

于是Up的第一个版本来了，模拟每一次切方块：

code(90#),最后一个点tle了，嗯.......,再想想，经过长达两年半的时间up终于悟出了，优化方案！

（见最下方code:）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
ll x,y,c,k,ans,tmp;
void solve() {cin>>x>>y;c=max(x,y),k=min(x,y);while(true) {ans=ans+(4*k);if((c==1&&k==1)||(c==0||k==0))break;c-=k;if(c<k) tmp=c,c=k,k=tmp;}cout<<ans<<"n";
}
int main() {ios::sync_with_stdio(false);solve();return 0;
}

优化

思路是这样子的：我们原本我们是模拟，每一次切方块，每一次！，思考思考是否我们这需要模拟每一次呢！，换句话说：我们真的的有必要一次一次的砍掉嘛！不~

（咸鱼翻身！）：我们只要求出当前长宽的情况，最多可以切出多少个最大方块，然后一次性把这些方块都剪掉（o1复杂度），这样子就可以大大降低时间复杂度

okk上ACcode(配上注释，安全食用~)

ACcode:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
ll x,y,c,k,ans,tmp;
void solve() {cin>>x>>y;c=max(x,y),k=min(x,y);while(c!=0&&k!=0) {ans=ans+(c/k)*(4*k);//个数*周长 //（c/k）：求出当前还可以在c还大于k的情况下，我们可以最多切可长度为k的正方形 c%=k;//c切（c/k）个正方形后的长度 if(k>c)tmp=k,k=c,c=tmp;//重新计算当前的长宽（以为经过上面操作，宽可能大长） }cout<<ans<<"n";
}
int main() {ios::sync_with_stdio(false);solve();return 0;
}

over~