CF1278B A and B

好久沒寫題解了，今天更新一波~~~
題目大意：

給定兩個數(shù)aa和bb，第ii次的操作可以選一個數(shù)增加ii（僅能增加i并且只能增加一次），求讓aa和bb相等最小操作次數(shù)。

分析：

開始a,b,x=abs(a?b) ,現(xiàn)在要求±1±2±3…±n=x

我們一直加直到超過x時停下:

1+2+3…+n=x+y(剛好超過了x,加到了x+y).

Ⅰ.當(dāng)y為偶數(shù),那么前面有一次 2/y我們不加,而是減去它,就得到了x

這 種 情 況 下 , 只 需 要 操 作 n 次 即 可 ( 一 定 最 優(yōu) )

Ⅱ.y為奇數(shù),此時y不能被2整除

那 我 們 就 構(gòu) 造 出 新 的 y 為 偶 數(shù)

Ⅱ.1. 當(dāng)n+1為奇數(shù)時

1 + 2 + 3… + ( n + 1 ) = x + y ( 此 時 y 被 構(gòu) 造 成 了 偶 數(shù) )

那 么 這 時 候 需 要 操 作 n + 1 次

Ⅱ.2. 當(dāng)n+1為偶數(shù)，那么n+2為奇數(shù)

1 + 2 + 3… + ( n + 2 ) = x + y ( 此 時 y 被 構(gòu) 造 成 了 偶 數(shù) )

那 么 此 時 需 要 操 作 n + 2 次

附上AC code

#include <bits/stdc++.h> using namespace std; #define int long long int n,m,t; int main() {cin>>t;while(t--){cin>>n>>m;int x=abs(n-m);int l=0,r=1e6,mid;while(r>l){mid=(l+r)/2;if(mid*(mid-1)/2+mid>=x) r=mid;else l=mid+1;}int y=r*(r-1)/2+r-x;if(y%2==0) cout<<r<<endl;else if((r+1)%2==1) cout<<r+1<<endl;else cout<<r+2<<endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的CF1278B A and B的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。