#include <iostream> #include <vector> #include <stdint.h> #include <algorithm> using namespace std; struct odcinek { int32_t miasta, konce, czasZyciaX2; odcinek(int32_t Miasta, int32_t Konce):miasta(Miasta), konce(Konce) { if (konce==2) czasZyciaX2 = miasta; else if (konce==1) czasZyciaX2 = miasta*2; else //(konce==0) czasZyciaX2 = 10*1000*1000; // nieskonczony } bool operator<(const odcinek other) {return czasZyciaX2 < other.czasZyciaX2;} }; void wczytajStan(uint32_t n, vector<odcinek>& lista) { uint32_t licznik=0, licz0=0; char ktore = '1'; int32_t konce = 2; // wczytanie danych o zarazeniach w n miastach while (licznik<n) { char c = '1'; cin>>c; licznik++; if (c=='0') { licz0++; if (licznik==1) konce--; if (licznik==n) { konce--; lista.push_back(odcinek(licz0, konce)); } if (ktore=='1') ktore = '0'; } else if (ktore=='0') // and c=='1' { lista.push_back(odcinek(licz0, konce)); licz0 = 0; konce = 2; ktore = '1'; } } } void zarazanie(vector<odcinek>& lista) { for (auto it=lista.begin(); it!= lista.end(); ++it) it->miasta -= it->konce; auto it = remove_if(lista.begin(), lista.end(), [](odcinek x){return x.miasta<1;}); lista.erase(it, lista.end()); } int main() { uint32_t ileTestow, n; cin>>ileTestow; for (uint32_t test=0; test < ileTestow; test++) { cin>>n; vector<odcinek> listaOdcinkow; int32_t bezpieczne = 0; wczytajStan(n, listaOdcinkow); sort(listaOdcinkow.begin(), listaOdcinkow.end()); while (listaOdcinkow.size()>0) { // szczepimy blok o najwiekszym czasie zycia if (listaOdcinkow.back().konce<2 || listaOdcinkow.back().miasta==1) { bezpieczne += listaOdcinkow.back().miasta; listaOdcinkow.pop_back(); } else // konce==2 i miasta>1 listaOdcinkow.back().konce--; // zarazanie zarazanie(listaOdcinkow); } cout<< n - bezpieczne <<endl; } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 | #include <iostream> #include <vector> #include <stdint.h> #include <algorithm> using namespace std; struct odcinek { int32_t miasta, konce, czasZyciaX2; odcinek(int32_t Miasta, int32_t Konce):miasta(Miasta), konce(Konce) { if (konce==2) czasZyciaX2 = miasta; else if (konce==1) czasZyciaX2 = miasta*2; else //(konce==0) czasZyciaX2 = 10*1000*1000; // nieskonczony } bool operator<(const odcinek other) {return czasZyciaX2 < other.czasZyciaX2;} }; void wczytajStan(uint32_t n, vector<odcinek>& lista) { uint32_t licznik=0, licz0=0; char ktore = '1'; int32_t konce = 2; // wczytanie danych o zarazeniach w n miastach while (licznik<n) { char c = '1'; cin>>c; licznik++; if (c=='0') { licz0++; if (licznik==1) konce--; if (licznik==n) { konce--; lista.push_back(odcinek(licz0, konce)); } if (ktore=='1') ktore = '0'; } else if (ktore=='0') // and c=='1' { lista.push_back(odcinek(licz0, konce)); licz0 = 0; konce = 2; ktore = '1'; } } } void zarazanie(vector<odcinek>& lista) { for (auto it=lista.begin(); it!= lista.end(); ++it) it->miasta -= it->konce; auto it = remove_if(lista.begin(), lista.end(), [](odcinek x){return x.miasta<1;}); lista.erase(it, lista.end()); } int main() { uint32_t ileTestow, n; cin>>ileTestow; for (uint32_t test=0; test < ileTestow; test++) { cin>>n; vector<odcinek> listaOdcinkow; int32_t bezpieczne = 0; wczytajStan(n, listaOdcinkow); sort(listaOdcinkow.begin(), listaOdcinkow.end()); while (listaOdcinkow.size()>0) { // szczepimy blok o najwiekszym czasie zycia if (listaOdcinkow.back().konce<2 || listaOdcinkow.back().miasta==1) { bezpieczne += listaOdcinkow.back().miasta; listaOdcinkow.pop_back(); } else // konce==2 i miasta>1 listaOdcinkow.back().konce--; // zarazanie zarazanie(listaOdcinkow); } cout<< n - bezpieczne <<endl; } return 0; } |