1.Problem - C - Codeforces
让我们从n个数中找出使得 周长p^2/面积s 最小的矩形,首先如果不思考直接枚举得到的是一个n^2复杂度的算法,我们可以尝试化简这个式子，假设我们的矩形是由a , a b , b四条边构成的那么
p^2 / s = (2 * a + 2 * b) ^ 2 / (a * b)化简完之后可以得到8 + 4 * (a / b + b / a),很明显这里可以使用基本不等式,a + b >= 2 * sqrt(a * b) 我们其中要想取等号也就是令a + b最小当且仅当a == b的时候,那么也就是a和b的差值越小值越小,那么对于i我们只需要找到n个数中大小位于i两边的数进行枚举就行,这样时间复杂度就是O(n)了,我们将所有出现过两次的边放进vector中排序然后每个数字只与相邻的数枚举选最小即可
#define yyy cout<<"Yes"<<"\n"
#define nnn cout<<"No"<<"\n"
#define x first
#define y second
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<ll , ll> pii;
typedef pair<int , string> pis;
const int N = 1e6 + 10,inf = 0x3f3f3f3f,mod = 1e9 + 7;
const double pi = 3.1415926535898;int n;
int a[N];void work()
{cin>>n;vector <ll> b;map <ll , int> mp;for(int i = 1 ; i <= n ; i++){cin>>a[i];mp[a[i]]++;if(mp[a[i]] == 2){b.push_back(a[i]);mp[a[i]] = 0;}}pii ans;double minn = 1e18;sort(b.begin() , b.end());for(int i = 0 ; i + 1 < b.size() ; i++){ll x = b[i],y = b[i + 1];double sum = (2 * x + 2 * y) * (2 * x + 2 * y) * 1.0 / (x * y);if(minn > sum){minn = sum;ans = {x , y};}}cout<<ans.x<<" "<<ans.x<<" "<<ans.y<<" "<<ans.y<<"\n";
}int main()
{std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int t;cin>>t;while(t--){work();}
}
2.C-小红打怪_牛客小白月赛104
二分答案,切记不能排序,最重要的是check函数,当我们固定mid回合后怎么最大化mid回合中的伤害呢,首先减去小红的全体伤害,然后将单体伤害和范围伤害分开考虑,使用次数分别是x和y,首先先考虑范围伤害当b[i]和b[i + 1]都大于0的时候使用范围,使用次数是min(b[i] , b[i+1]),遍历一遍之后剩下的都是单个存活的,这些都用单体伤害处理,我们需要看x和y的最大值是否小于等于mid,因此我们要最小化max(x , y),我们发现一个单体伤害可以由一个范围伤害平替换,因此x < y的时候我们令x = (x + y) / 2,y = (x + y + 1) / 2(哪个进一无所谓),若x > y,我们发现两个单体伤害可以平替一个范围伤害,也就是x - k = y + 2 * k ==> k = (x - y) / 3,因此令x = x - k,y = y + 2 * k,最后比较mid >= max(x , y)即可
#define yyy cout<<"Yes"<<"\n"
#define nnn cout<<"No"<<"\n"
#define x first
#define y second
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<ll , ll> pii;
typedef pair<int , string> pis;
const int N = 1e5 + 10,inf = 0x3f3f3f3f,mod = 1e9 + 7;
const double pi = 3.1415926535898;int n;
ll a[N],b[N];bool check(ll mid)
{for(int i = 1 ; i <= n ; i++){b[i] -= min(b[i] , mid);}ll x = 0,y = 0;for(int i = 1 ; i <= n ; i++){if(b[i] > 0 && b[i + 1] > 0){ll t = min(b[i] , b[i + 1]);b[i] -= t,b[i + 1] -= t;x += t;}}for(int i = 1 ; i <= n ; i++){if(b[i] > 0){y += b[i];}}if(y > x){y = (x + y + 1) / 2;}else if(y < x){ll k = (x - y) / 3;x -= k,y += 2 * k;}return mid >= max(x , y);
}int main()
{std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i = 1 ; i <= n ; i++){cin>>a[i];b[i] = a[i];}ll l = 1,r = 1e18;while(l < r){ll mid = (l + r) / 2;if(check(mid)){r = mid;}else{l = mid + 1;}memcpy(b , a , sizeof a);}cout<<r;
}
