VPARTSUM - Tổng bộ phận

Tác giả: hieult

Ngôn ngữ: C++

#include <iostream>
#include <cstdio>
//#include <conio.h>
//#include <algorithm>
//#include <alloc.h>

using namespace std;


class Node
{
    public:
    int info;
    Node* left;
    Node* right;
    Node (int x)
    {
        info = x; left = right = NULL;
    }
};

class BSTree
{
      
    public:
    Node* root;
    BSTree() {root=NULL;}
    bool isEmpty(){return(root==NULL);}
    void clear(){ root = NULL;}
    void visit(Node p)
    {
        //System.out.println(p.info);
    };

    void setRoot(int x)
    {
        root = new Node(x);

    }
    int max(int a,int b)
    {
        if(a>b) return a;
        return b;
    }
    /*
    Node search(Node* p,int x)
    {
        if( p == NULL || p->info ==x ) return p;
        if(x<p->info) return search(p->left,x);
        else return search(p->right,x);
    }
    */
    int Search(int x)
    {
        int k = tim(root,x);
        return k;
    }

    int tim(Node* p,int x)
    {
        if(p==NULL)
            return 0;
        if(p->info==x)
            return x;
        if(x<p->info)
            return tim(p->left,x);
        else return max(p->info,tim(p->right,x));
    }
    /*
    void insert(int x)
    {
        Node q = new Node(x);
        if(isEmpty()){root = q; return;}
        Node f,p; f= null; p=root;
        while(p!=null)
        {
             {if(p.info==x) {System.out.println(" The key already exists"); return;}
              f = p;
              if(x<p.info) p=p.left; else p=p.right;
             }
            if(x<f.info) f.left=q; else f.right=q;
        }
    }

     */
  void insert(int x)
   {Node* q = new Node(x);
    if(isEmpty()) {root=q;return;}
    Node *f,*p;f=NULL;p=root;
    while(p!=NULL)
     {if(p->info==x) {//System.out.println(" The key already exists");
          return;}
      f = p;
      if(x<p->info) p=p->left; else p=p->right;
     }
    if(x<f->info) f->left=q; else f->right=q;
   }
  /*
    void preOrder(Node p)
    {
        if(p==null) return;
        visit(p);
        preOrder(p.left);
        preOrder(p.right);
    }
    void inOrder(Node p)
   {
    if(p==null) return;
    inOrder(p.left);
    visit(p);
    inOrder(p.right);
   }
    void postOrder(Node p)
   {if(p==null) return;
    postOrder(p.left);
    postOrder(p.right);
    visit(p);
   }
    void breadthTraverse()
    {
        MyQueue q = new MyQueue();
        q.enqueue(root);
        Node p;
        while(!q.isEmpty())
        {
            p = (Node) q.dequeue();
            visit(p);
            if(p.left!=null) q.enqueue(p.left);
            if(p.right!=null) q.enqueue(p.right);
        }
    }
    void dele(int x)
    {
        Node f,p; f=null; p=root;
        while(p!=null)
        {
            if(p.info == x) break;
            f=p;
            if(x<p.info) p=p.left; else p = p.right;
        }
        if (p==null){ System.out.println("...");}
        if(p.left == null && p.right == null)
        {
            if(f==null ){root=null;return;}
            if(f.left==p)f.left=null; else f.right = null;
        }

        if(p.left !=null &&p.right==null)
        {
            if(f==null ){root=p.left;return;}
            if(f.left==p)f.left=p.left; else f.right = p.left;

        }
        if(p.left ==null &&p.right!=null)
        {
            if(f==null ){root=p.right;return;}
            if(f.left==p)f.left=p.right; else f.right = p.right;

        }
        if(p.left !=null &&p.right!=null)
        {
            Node rp ,frp;
            frp = p;rp =p.left;
            while(rp.right!=null)
            {
                frp = rp;rp=rp.right;
            }
            p.info = rp.info;
            frp.right=rp.left;
        }
    }
    void delebyMerging(int x)
    {
        Node f,p; f=null; p=root;
        while(p!=null)
        {
            if(p.info == x) break;
            f=p;
            if(x<p.info) p=p.left; else p = p.right;
        }
        if (p==null){} //System.out.println("...");}
        if(p.left == null && p.right == null)
        {
            if(f==null ){root=null;return;}
            if(f.left==p)f.left=null; else f.right = null;
        }

        if(p.left !=null &&p.right==null)
        {
            if(f==null ){root=p.left;return;}
            if(f.left==p)f.left=p.left; else f.right = p.left;

        }
        if(p.left ==null &&p.right!=null)
        {
            if(f==null ){root=p.right;return;}
            if(f.left==p)f.left=p.right; else f.right = p.right;

        }
        if(p.left !=null &&p.right!=null)
        {
            Node q=p.right;
            p.right=null;
            Node lp = p.left;
            if(f.left==p) f.left = lp; else f.right=lp;
            Node rp ;
            rp = lp;
            rp =p.left;
            while(rp.right!=null)
            {
                rp=rp.right;
            }
            rp.right=q;
        }
    }
    void addMany(int [] a)
    {
        for(int i=0;i<a.length;i++)
            insert(a[i]);
    }
*/ 
};

int main()
{
     //freopen("VPARTSUM.in","r",stdin);
     int n,k,p,a;
     int tong = 0;
     BSTree t;
     scanf("%d %d %d",&n,&k,&p);
     int KQ = p;
     for(int i = 1;i<=n;i++)
        {
            scanf("%d",&a);
            tong = (tong + a)%p;
            int x = tong-k,y;
            if(x<0) x+=p;
            y = t.Search(x);
            //(tong+" "+x+" "+y);
            y = tong - y;
            if(y<0) y+=p;
            if(y<KQ) KQ = y;
            t.insert(tong);
        }
        printf("%d",KQ);
        //getch();
}

Download