đó là problem D trong đề thi ACM ngày 27/10/2012
tóm tắt như sau. trong 1 dãy số, 1 số được gọi là local min nếu số trước và sau nó đều> nó, local max nếu số trước và sau đều < nó. bài cho 1 dãy số, đếm local min và local max
ví dụ input dãy số 4 1 2 1 3, số đầu tiên là số phần tử(4), 1 2 1 3 là dãy. output là 1 1(1 local min, 1 local max)
mình code bằng c++, bạn mình code bằng java, 2 đứa y hệt nhau mà nó AC mình WA, làm mất hơn nửa thời gian vì cái bài này, mà cuối cùng vẫn bị cho là không đúng.
đây là code của mình và bạn mình, bạn nào tốt bụng xem hộ với, mình dùng dev c++, bạn mình là eclipse
Code: |
#include <cstdlib>
#include <iostream>
using namespace std;
int main(int argc, char *argv[])
{
int n;
long long a[1000];
bool firstblood = true;
while(true)
{
cin>>n;
if(n==0) break;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int min=0;int max=0;
for(int i=1;i<n-1;i++)
{
if(a[i]>a[i-1] && a[i]>a[i+1])
max++;
else if(a[i]<a[i-1] && a[i]<a[i+1])
min++;
}
if(firstblood){firstblood = false;} else {cout<<endl;}
cout<<min<<" "<<max;
}
system("PAUSE");
return 0;
}
|
Code: |
import java.util.ArrayList;
import java.util.Scanner;
public class ContestD {
/**
* @param args
*/
@SuppressWarnings("resource")
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner ScanTest=new Scanner(System.in);
ArrayList<String>ListInput=new ArrayList<String>();
int N=ScanTest.nextInt();
while(N!=0)
{
String Data =ScanTest.nextLine();
ListInput.add(Data.trim());
N=ScanTest.nextInt();
}
// System.out.println(ListInput.size());
for(int i=0;i<ListInput.size();i++)
{
int Max=0,Min=0;
String []tmp=ListInput.get(i).split(" ");
int[]arr=new int[tmp.length];
for(int j=0;j<arr.length;j++)
{
arr[j]=Integer.parseInt(tmp[j]);
}
for(int k=1;k<arr.length-1;k++)
{
if(arr[k]>arr[k-1]&&arr[k]>arr[k+1])Max++;
if(arr[k]<arr[k-1]&&arr[k]<arr[k+1])Min++;
}
if(i<ListInput.size()-1)System.out.println(Min+" "+Max);
else System.out.print(Min+" "+Max);
}
}
}
|