Pagini recente » Cod sursa (job #1865112) | Cod sursa (job #1510453) | Cod sursa (job #465586) | Cod sursa (job #1978229) | Cod sursa (job #786175)
Cod sursa(job #786175)
#include <stdio.h>
#include <fstream>
#include <list>
#define MAX 500005
using namespace std;
FILE *fout, *fileread;
int maxEl=-35000, pos=0 ;
int N, K;
int secv[MAX];
char numbers[MAX];
void quickFileRead(){
int j=0, order;
fileread = fopen("secventa.in", "r");
fscanf(fileread, "%d %d\n", &N, &K);
fgets(numbers, sizeof(numbers), fileread);
for(int i =0; i< N; i++){
secv[i]=0;
order = 0;
while(numbers[j]!='-' &&
(numbers[j]<'0' || numbers[j]> '9'))
j++;
if(numbers[j]=='-'){
order = 1;
j++;
}
while(numbers[j]>='0' && numbers[j]<='9'){
secv[i]=secv[i]*10+(numbers[j]-'0');
j++;
}
if(order)
secv[i] =-secv[i];
}
fclose(fileread);
}
void process(){
ifstream indata("secventa.in");
list<int> orderedElements;
int i;
indata >> N >> K;
for(i =0; i< N; i++)
indata >> secv[i];
for(i = 0; i< K; i ++ ){
while(!orderedElements.empty() &&
secv[i] <= secv[orderedElements.back()])
orderedElements.pop_back() ; // remove the last element
orderedElements.push_back(i);
}
maxEl = secv[orderedElements.front()];
for (i = K; i < N; i ++){
if(orderedElements.front() == i - K )
orderedElements.pop_front();
while(!orderedElements.empty() &&
secv[i] <= secv[orderedElements.back()])
orderedElements.pop_back(); // remove the last element
orderedElements.push_back(i);
// when we are done with one iteration store the current min val
if (secv[orderedElements.front()] > maxEl){
maxEl = secv[orderedElements.front()];
pos = i-K+1;
}
}
}
void store(){
// store the results
fout=fopen("secventa.out","w");
fprintf(fout,"%d %d %d",pos + 1,
pos + K ,
maxEl);
fclose(fout);
}
int main(int argc, char* argv[]) {
quickFileRead();
process();
store();
return 0;
}