第三周周赛题
虽然简单但也简单记录一下
题目传送门
You are developing a project to build a new data center. The data center will be a rectangle with an area of exactly n square meters. Each side of the data center must be an integer.
Your goal is to minimize the impact of the external environment on the data center. For this reason, you want to minimize the length of the perimeter of the data center (that is, the sum of the lengths of its four sides).
What is the minimum perimeter of a rectangular data center with an area of exactly n square meters, if the lengths of all its sides must be integers?
Input
The first and only line of the input contains an integer n (1≤n≤105), where n is the area of the data center in square meters.
Output
Print the required minimum perimeter in meters.
Examples
Input
36
Output
24
Input
13
Output
28
Input
1
Output
4
Note
In the first example, the required shape of the data center is 6×6 square. Its area is 36 and the perimeter is 6+6+6+6=24.
In the second example, the required shape of the data center is 1×13 rectangle. Its area is 13 and the perimeter is 1+13+1+13=28.
In the third example, the required shape of the data center is 1×1 square. Its area is 1 and the perimeter is 1+1+1+1=4.
题意：简单
思路：设边长，利用已知去枚举解即可。
做题时：我想得不够缜密，就按照题意枚举，但对于得出的那个结果来说有一代女
我们只需枚举长方形一边的长度，如果面积是这个长度的倍数，那么面积除以该长度就是另一边的长度，然后更新长方形周长最大值并且保证自己所枚举的两边乘积等于面积将即可。
时间复杂度:O(n)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int n;
scanf("%d",&n);
ll sum=999999999999,ans,y;
for(int i=1;i<=10000;i++)
{
ll yy=2*n;
yy=yy/i;
ans=2*i+yy;
ll xx=n/i;
if(ans<sum&&xx*i==n){
sum=ans;
y=i;
}
}
sum=n/y;
//cout<<y<<" "<<sum<<endl;
printf("%lld",2*sum+2*y);
return 0;
}
错误代码：
错误原因，枚举时候没有保证面积等于n；
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int n;
scanf("%d",&n);
ll sum=999999999999,ans,y;
for(int i=1;i<=10000;i++)
{
ans=(2*i*i+2*n)/i;
if(ans<sum){
sum=ans;
y=i;
}
}
sum=n/y;
printf("%lld",2*sum+2*y);
return 0;
}
You are given an array a1,a2,…,an.
In one operation you can choose two elements ai and aj (i≠j) and decrease each of them by one.
You need to check whether it is possible to make all the elements equal to zero or not.
Input
The first line contains a single integer n (2≤n≤105) — the size of the array.
The second line contains n integers a1,a2,…,an (1≤ai≤109) — the elements of the array.
Output
Print “YES” if it is possible to make all elements zero, otherwise print “NO”.
Examples
Input
4
1 1 2 2
Output
YES
Input
6
1 2 3 4 5 6
Output
NO
Note
In the first example, you can make all elements equal to zero in 3 operations:
Decrease a1 and a2,
Decrease a3 and a4,
Decrease a3 and a4
In the second example, one can show that it is impossible to make all elements equal to zero.
思路
如果总和为奇数，必定不可能构造 否则总和为偶数。
如果存在最大值>总和-最大值，那么必定无解 否则必定有解。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MM=1e6+6;
ll a[MM];
int main()
{
int n;
scanf("%d",&n);
ll sum=0,ans=0;;
for(int i=0; i<n; i++)
{
scanf("%lld",&a[i]);
ans+=a[i];
if(sum<a[i])
sum=a[i];
}
if(ans%2==0&&ans-sum>=sum)//当和为偶数，和减去最大值大于等于最大值
printf("YES\n");
else
printf("NO\n");
return 0;
}
