Cod sursa(job #349284)

Utilizator ucc_5Usurelu Catalin ucc_5 Data 18 septembrie 2009 22:00:40
Problema Litere Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
//pentru s[i] vedem cate litere sunt mai mari decat s[i] in sirul s[1..i-1] (acesta e numarul de inversiuni necesare
//pentru a aduce pe s[i] pe pozitia corecta
#include <fstream>
#define NMax 10003
using namespace std;
ifstream f("litere.in");
ofstream g("litere.out");

using namespace std;

int n,inv,aux[27];
char s[NMax];  //aux[i]-frecventa literei i pana in momentul respectiv

void citire ()
{
  f>>n;
  for (int i=1; i<=n; i++)
  {
	f>>s[i];
	s[i]=s[i]-'a'+1;
  }
  f.close ();
}

void nr_inversiuni ()
{
  int i,j,k;
  for (i=1; i<=n; i++)
  {
	aux[s[i]]++;
	for (k=1; k<=26; k++)
	  if (k>s[i])
		inv+=aux[k];
  }
}

int main ()
{
  citire ();
  nr_inversiuni ();
  g<<inv;
  g.close (); return 0;
}