南通网站建设方案外包,图片主题wordpress,thea wordpress,卖视频会员个人网站怎么做传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a; 思路#xff1a;
针灸思维不行#xff0c;数据结构来凑呗。 一开始做的时候想简单了#xff0c;一直wawawa#xff0c;后来想到了hackhackhack样例#xff0c;开始换思路构造#xff0c;结果死活想不到…传送门
文章目录题意思路题意 思路
针灸思维不行数据结构来凑呗。 一开始做的时候想简单了一直wawawa后来想到了hackhackhack样例开始换思路构造结果死活想不到O(m)O(m)O(m)怎么构造所以用堆维护写了个mlogmmlogmmlogm的。 首先[1,m][1,m][1,m]肯定是放在[1,m][1,m][1,m]对应的位置是最优的所以当∑lin\sum l_in∑lin或者ili−1nil_i-1nili−1n就无解。 那么满足如上条件后我们将每个数都放在了[1,m][1,m][1,m]的位置上现在保证了每个颜色都出现了至少一次了但是我们没有保证所有的都被涂色因为右边有可能空出来一块所以我们考虑将一部分右移。这里我右移的部分是整个一块右移即将[l,m][l,m][l,m]右移所以我们维护一个堆里面一开始放着ili−1il_i-1ili−1从111开始维护一个sumsumsum表示左边长度deldeldel表示要减去多少每次都让sumsuma[i]sumsuma[i]sumsuma[i]之后看一下sumq.top()−delnsumq.top()-delnsumq.top()−deln不满足继续i1i1i1否则就从当前长度一直减到sumq.top()−delnsumq.top()-delnsumq.top()−deln的时候停下从这里填就好啦。
// Problem: C. Dreamoon Likes Coloring
// Contest: Codeforces - Codeforces Round #631 (Div. 2) - Thanks, Denis aramis Shitov!
// URL: https://codeforces.com/contest/1330/problem/C
// 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
#includeassert.h
#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].r1)
#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,m;
int a[N],pos[N];
int suf[N];bool check() {LL sum0;for(int i1;im;i) {suma[i];if(ia[i]-1n) return false;}if(sumn) return false; priority_queuePIIq;for(int i2;im;i) q.push({ia[i]-1,-i});sum0; int del1;for(int i1;im;i) {pos[i]sum1;suma[i];if(!q.size()) break;while(-q.top().Yi) q.pop();if(sumq.top().X-deln) {while(sumq.top().X-deln) sum--;sum;for(int ji1;jm;j) pos[j]sum;break;} del;}for(int i1;im;i) printf(%d ,pos[i]);return true;
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d%d,n,m);for(int i1;im;i) scanf(%d,a[i]);if(!check()) {puts(-1);return 0;}return 0;
}
/**/
