贪心-牛客多校第一场
https://ac.nowcoder.com/acm/contest/881/C
貌似只把问题带到了数列上就会变简单一点？？？？
先把原题读一遍，再看下面的解释
有一个长度为n(1e4)的序列a:每个元素的范围是[1,1e3]
你需要构造一个序列b:b中的每个元素要大于等于0，sum：b[1,n]要等于m
求min
于是，类似于你可以花费b[i]的和来减少某个a[i]的值:如何是的a[i]的平方和最小
方法当然是:每次使用eps个花费,都放在最大的a[i]身上
于是，贪就完了:
/////////////////////////////////////////Info/////////////////////////////////////////////////
//Problem:
//Date:
//Skill:
//Bug:
/////////////////////////////////////////Definations/////////////////////////////////////////////////
//循环控制
#define CLR(a) memset((a),0,sizeof(a))
#define F(i,a,b) for(int i=a;i<=int(b);++i)
#define F2(i,a,b) for(int i=a;i>=int(b);--i)
#define RE(i,n) for(int i=0;i<int(n);i++)
#define RE2(i,n) for(int i=1;i<=int(n);i++)
//简化敲击
#define PII pair<int,int>
#define PDD pair<double,double>
#define PLL pair<long long ,long long>
#define PB push_back
#define MODY(n) (n%=mod)<0?n+=mod:n
#define MODED(n) ((n)<0?(n)%mod+mod:(n)%mod)
#define x first
#define y second
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const long long llinf = 0x3f3f3f3f3f3f3f3f;
////////////////////////////////////////Options//////////////////////////////////////////////////////
#define stdcpph
#ifdef stdcpph
#include<bits/stdc++.h>
#else
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<algorithm>
#include<functional>
#include<iostream>
#include<iomanip>
#include<string>
#include<stdio.h>
#endif
////////////////////////////////////////Basic Functions//////////////////////////////////////////////
template<typename INint> inline void IN(INint &x)
{
x = 0; int f = 1; char c; cin.get(c);
while (c<'0' || c>'9') { if (c == '-')f = -1; cin.get(c); }
while (c >= '0'&&c <= '9') { x = x * 10 + c - '0'; cin.get(c); }
x *= f;
}
template<typename INint> inline void OUT(INint x)
{
if (x > 9)OUT(x / 10); cout.put(x % 10 + '0');
}
////////////////////////////////////////Added Functions//////////////////////////////////////////////
const int maxn = int(1e4+8);
#define sq(x) ((x)*(x))
ll n, m;
ll a[maxn];
template<typename T>
T gcd(T a, T b)
{
if (a < b)swap(a, b);
return b == 0 ? a : gcd(b, a%b);
}
////////////////////////////////////////////Code/////////////////////////////////////////////////////
int main()
{
//freopen("C:\\Users\\VULCAN\\Desktop\\data.in", "r", stdin);
int T(1), cas(0);
#ifdef CPP_IO// CPP_IO
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//cin >> T;
#endif
/////////////////////////////////////////////////////////////////////////////////////////////////
while (cas, T--, cin >> n >> m)
{
F(i, 1, n)cin >> a[i]; a[n + 1] = -inf;
sort(a + 1, a + 1 + n); reverse(a + 1, a + 1 + n);
ll ri, sum, res = m;
F(i, 1, n)
{
if (i*(a[i] - a[i + 1]) <= res)
{
res -= i * (a[i] - a[i + 1]);
}
else
{
ri = i;
sum = i * a[i] - res;
break;
}
}
//sum*sum/ri
ll ans(0);
F(i, ri + 1, n)
{
ans += a[i] * a[i];
}
ans = ans * ri + sum * sum;
ll fenmu = m * m*ri;
ll g = gcd(ans, fenmu);
ans /= g; fenmu /= g;
cout << ans;
if (fenmu != 1)cout << '/' << fenmu;
cout << endl;
}
///////////////////////////////////////////////////////////////////////////////////////////////////
return 0;
}
//What to Debug
/*
-1.最好把全部warning都X掉,否则:https://vjudge.net/solution/19887176
0.看看自己是否有可能需要快读，禁endl
1.数组越界，爆int,浮点精度(查看精度是否达到题目要求,看有没有浮点数比较:eps)，取模操作，初始化数组，边缘数据,输出格式(cas)
2.通读代码，代码无逻辑错误
3.读题，找到题意理解失误或算法错误
4.放弃
*/
查看30道真题和解析