【ブルーブリッジカップ】アリ風邪(C++)
3084 ワード
問題は長さ100センチの細長い直棒にn匹のアリがいることを示している.頭は左に向いている人もいれば、右に向いている人もいます.
どのアリも棒に沿って前に登るしかなく、速度は1センチ/秒です.
2匹のアリが会うと、同時に反対の方向に頭を下げて登ります.
これらのアリのうち、1匹が風邪を引いた.そして他のアリと会うと、風邪を出会ったアリに伝染します.
すべてのアリが棒から這い出したとき、どれだけのアリが風邪を引いたか計算してください.入力フォーマットの最初の行には、アリの総数を表す整数n(1次の行は、スペースで区切られたn個の整数Xi(−100思想:まず私たちは知っていて、もし1対のアリが互いに向かい合っているならば、この2匹のアリの左右の2匹のアリはきっと彼らと直面しません.アルゴリズム1、私達はすべてのアリの対(互いに向かい合う)距離の最も小さい(多対あるかもしれない)がminnであることを探し出して、2、すべてのアリはminn/2個の距離の3を移動して、しかも距離の最も小さいアリの対、方向を逆にして、感染状態を更新して、4、まだ直面しているアリがあって、あるいは残りのアリの数は0ではありませんて、1を引き続き実行して、さもなくば終わります
どのアリも棒に沿って前に登るしかなく、速度は1センチ/秒です.
2匹のアリが会うと、同時に反対の方向に頭を下げて登ります.
これらのアリのうち、1匹が風邪を引いた.そして他のアリと会うと、風邪を出会ったアリに伝染します.
すべてのアリが棒から這い出したとき、どれだけのアリが風邪を引いたか計算してください.入力フォーマットの最初の行には、アリの総数を表す整数n(1
#include
#include
#include
using namespace std;
struct ant{ //
double loc;
int dir;
int inf;
ant(double ll,int dd,int ii){
loc = ll;
dir = dd;
inf = ii;
}
};
bool cmp(const ant&a,const ant&b){
return a.loc < b.loc;
}
vectorvc; //
int main(){
int n;
cin>>n;
for(int i = 0;i < n;i++){ // vc
int t;
cin>>t;
if(t < 0){
if(i == 0){
vc.push_back(ant(abs(t),-1,1));
}else{
vc.push_back(ant(abs(t),-1,0));
}
}else{
if(i == 0){
vc.push_back(ant(abs(t),1,1));
}else{
vc.push_back(ant(abs(t),1,0));
}
}
}
sort(vc.begin(),vc.end(),cmp); //
int l = 0;//
int r = vc.size() - 1;//
while(l < r){ // 0
vectortvc; // ，
double minn = 666;
for(int i = l;i < r;i++){
if(vc[i].dir == 1 && vc[i+1].dir == -1 ){ //
if(minn > vc[i + 1].loc - vc[i].loc){
while(tvc.size() != 0){ // ，
tvc.pop_back();
}
tvc.push_back(i);
minn = vc[i + 1].loc - vc[i].loc;
}else{
if(minn == vc[i + 1].loc - vc[i].loc){ // ， tvc （ ）
tvc.push_back(i);
}
}
}
}
if(tvc.size() == 0){ //
break;
}
int ll = l;
int rr = r;
for(int i = ll;i <= rr;i++){ // minn/2
if(vc[i].dir == 1){
vc[i].loc += minn / 2;
}else{
vc[i].loc -= minn/2;
}
if(vc[i].loc >= 100){ //
r--;
}else{
if(vc[i].loc <= 0){ //
l++;
}
}
}
int ts = tvc.size();
for(int i = ts - 1;i >= 0;i--){ // （ ）
if(vc[tvc[i]].inf || vc[tvc[i] + 1].inf){ // ，
vc[tvc[i]].inf = 1;
vc[tvc[i] + 1].inf = 1;
}
vc[tvc[i]].dir *= -1; //
vc[tvc[i] + 1].dir *= -1; //f
tvc.pop_back(); // （ ， ， ）
}
}
int sum = 0;
for(int i = 0;i < n;i++){ //
if(vc[i].inf){
sum++;
}
}
cout<