题解 | #手串#
手串
http://www.nowcoder.com/questionTerminal/0bb1fad52f474bdaa4d7636ca3a98244
题目要求我们判断手串中不符合条件的颜色。显然这道题目有两个元素,一个是珠子的位置,一个是颜色所在珠子的位置。
思路:按颜色索引,用二维vector存储每种颜色所在位置,再依次判断每种颜色的位置是否合法。难点在于,珠子是成环状的,那么如何判断两个位置在环的条件下是否符合条件呢?事实上,画图分析后很容易发现,珠子i和j的位置实际上有两个,一个是abs(i-j),一个是n-abs(i-j)。这样就很明显了,当两个位置中有任意一个小于等于m时,即为非法。
#include <iostream>
#include <vector>
using namespace std;
int n, m, c, num_i, kind, sum;
bool check(int n, int m, vector<int>& posi){
if(posi.size() == 1){
return true;
}
for(int i = 0; i < posi.size(); i++){
for(int j = i + 1; j < posi.size(); j++){
int dis = abs(posi[i]-posi[j]);
//判断位置合法与否
if( dis <= m-1 || n - dis <= m-1){
//cout<<posi[i]<<" "<<posi[j]<<endl;
return false;
}
}
}
return true;
}
int main()
{
cin >> n >> m >> c;
vector<vector<int>> pos(c + 1);
for (int i = 1; i <= n; i++) {
cin>>num_i;
while(num_i--){
cin>>kind;
pos[kind].push_back(i);
}
}
for(int i = 1; i <= c; i++ ){
//逐个颜色进行check
if(!check(n,m,pos[i])){
sum++;
}
}
cout<<sum<<endl;
return 0;
}