题目
t(t
每次服务器托管网给定一个数n(n
n个魔方需要放在m(m
第i个架子的彩色度，定义为最近的两个颜色相同的魔方之间的距离，
如果第i个架子上不存在两个颜色相同的魔方，则彩色度为架子上魔方的个数，即si
第i个架子有一个限制di(1
输出m个架子构造的魔方序列，
如果不存在合法序列，输出-1
思路来源
潼神b站讲解
题解
似乎很难证这样的正确性，但可以感性理解一下，这样做不会比其他更劣
做法是，先将魔方统计每种颜色出现的个数，
维护一个set，set按出现次数从多到少排序，多的在前面
对于每个架子si，彩色度的最小限制di，意味着，每di个数都两两不同，
即将架子划分成了若干个长度为di的区间（最后一个区间可能小于di）
那么，每个区间内填的这di个数，是从set里取的出现次数最多的di种数，
如果set内数的种类数不足di，则输出无解
填完之后，对于每种数的出现次数减1，然后如果还剩有次数，就放回set
首先，这样肯定能保证两个相同的数的距离>=di，
因为考虑第x段的数v和第x+1段的数v之间的数，
出现在第x段的数，一定不为v，
出现在第x+1段v前面的数，其出现次数大于等于v的出现次数，
v没有用完，则这些数也没有用完，
所以本次的偏移量只会等于上次的偏移量，为di
其实我感觉，按si从大到小排序，会显得更贪心一些，
因为颜色种类数一开始有很多，后面就变少了
不太好举反例，而且潼神是按输入的si顺序操作的，也通过了，就姑且这样吧
代码
// Problem: D. Colorful Constructive
// Contest: Codeforces - Codeforces Round 908 (Div. 1)
// URL: https://codeforces.com/contest/1893/problem/D
// Memory Limit: 512 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include
using namespace std;
typedef long long ll;
#define pb emplace_back
struct St{
int cnt, num;
bool operator b.cnt;
return num ans[200005];
void solve(){
int n, m; cin >> n >> m;
for (int i = 1; i > x;
cnt[x]++;
}
set s;
for (int i = 1; i > a[i];
for (int i = 1; i > b[i];
for (int i = 1; i 0){
int t = min(a[i], b[i]);
a[i] -= t;
if (s.size() 1) s.insert({j.cnt - 1, j服务器托管网.num});
}
}
}
for (int i = 1; i > T;
while (T--){
solve();
}
}服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
相关推荐: 【scikit-learn基础】–『监督学习』之 支持向量机回归
在机器学习中，支持向量机（Support Vector Machine）算法既可以用于回归问题，也可以用于分类问题。 支持向量机（SVM）算法的历史可以追溯到1963年，当时前苏联统计学家弗拉基米尔瓦普尼克（Vladimir N. Vapnik）和他的同事阿列…
