mihaimarcel21

String_Streak_incercare6pct

Nov 29th, 2020
515
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. string A, B;
  5. int k, n, fr;
  6. char ch;
  7. char findMaxFrequency(string s, int &frecv)  /// caut ch cu cea mai mare frecventa
  8. {
  9.     unordered_map<char, int> Hash;
  10.     sort(B.begin(), B.end());
  11.     for(int i=0; s[i]; i++)
  12.             Hash[s[i]]++;
  13.     int max_count = 0;
  14.     char res;
  15.     for(auto i : Hash) {
  16.         if(max_count < i.second) {
  17.             res = i.first;
  18.             max_count = i.second;
  19.         }
  20.     }
  21.     frecv=max_count;   /// frecventa maxima si
  22.     return res;   /// caracterul
  23. }
  24. unsigned long long power(int x, unsigned int y)
  25. {
  26.     unsigned long long res = 1;
  27.     while (y > 0)
  28.     {
  29.         if (y & 1)
  30.             res =1ULL* res * x;
  31.  
  32.         y = y >> 1;
  33.         x = x * x;
  34.     }
  35.     return res;
  36. }
  37. int findLen(string& A, int n, int k, char chr)  /// aici caut sa modific
  38. {                                       /// chr este caracaterul cu fr cea mai mare
  39.     int l=0, r=0, p=1,cnt=0;
  40.     for(int i=0; A[i] && k; i++)///parcurg sirul cat timp am euro(k) si am caractere in sir
  41.         if(A[i]!=chr)    /// daca difera stabilesc interval si numar cate difera
  42.             ++r, cnt++;
  43.         else
  44.         {
  45.             p=power(2,r-l+1);   /// acesta este costul unui interval
  46.             k-=p;  /// scad costul intervalului ....
  47.             int j=i;
  48.             while(A[j]==chr && A[j])  /// daca nu difera parcurg numai
  49.                 j++;
  50.             if(A[j]) /// daca mai am caractere
  51.             {
  52.                 i=j-1;
  53.                 l=j;
  54.                 r=j;
  55.             }
  56.         }
  57.         return cnt;
  58. }
  59.  
  60. int main()
  61. {
  62.     getline(cin,A);
  63.     cin>>k;
  64.     B.assign(A);
  65.     n=A.size();
  66.     ch=findMaxFrequency(B,fr);
  67.     cout<<findLen(A, n, k, ch) + fr;
  68.     return 0;
  69. }
  70.  
RAW Paste Data