一级a做爰视频安全网站,品牌名字大全,网页设计师培训和继续教育的机会,仿站违法吗传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你一个长度为nnn的序列aaa#xff0c;你需要将其分成若干组#xff0c;每组的价值为max(ai)−min(ai)\max(a_i)-min(a_i)max(ai)−min(ai)#xff0c;求如何分组才能使得代价最小#xff0c;输出…传送门
文章目录题意思路题意
给你一个长度为nnn的序列aaa你需要将其分成若干组每组的价值为max(ai)−min(ai)\max(a_i)-min(a_i)max(ai)−min(ai)求如何分组才能使得代价最小输出最小代价以及分组方案。 3≤n≤2e5,1≤ai≤1e93\le n\le2e5,1\le a_i\le1e93≤n≤2e5,1≤ai≤1e9
思路
首先可以将这个数组排个序不过要在排序之前记录一下编号。 排序之后就可以大力dpdpdp了定义f[i]f[i]f[i]表示到了第iii个数的最小代价那么肯定是从[1,i−3][1,i-3][1,i−3]转移过来但是这样转移是n2n^2n2的需要优化一下。 通过多写几组可以发现我们如果分出来了个长度为666的组那么把它分成俩长度为333的组答案一定不会变劣。所以我们只需要从[i−6,i−3][i-6,i-3][i−6,i−3]转移过来那么转移方程就是f[ij]min(f[ij],f[i−1]a[ij].val−a[i].val)f[ij]min(f[ij],f[i-1]a[ij].val-a[i].val)f[ij]min(f[ij],f[i−1]a[ij].val−a[i].val) 输出方案的时候记录一下组数就好啦没有要求组数最少随便找一组即可。
// Problem: E. Yet Another Division Into Teams
// Contest: Codeforces - Codeforces Round #598 (Div. 3)
// URL: https://codeforces.com/contest/1256/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n;
LL f[N];
int ans[N],tot;
struct Node {int val,id;bool operator (const Node W) const {return valW.val;}
}a[N];int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d,n);for(int i1;in;i) scanf(%d,a[i].val),a[i].idi;sort(a1,a1n);memset(f,INF,sizeof(f));f[0]0;for(int i1;in;i) {for(int j2;j5;j) f[ij]min(f[ij],f[i-1]a[ij].val-a[i].val);}for(int in;i1;) {for(int j3;j5;j) if(i-j0f[i]f[i-j]a[i].val-a[i-j1].val) {tot;for(int hi-j1;hi;h) ans[a[h].id]tot;i-j;break;}}coutf[n] totendl;for(int i1;in;i) printf(%d ,ans[i]); puts();return 0;
}
/**/
