2018-03-10 STL

优先队列
结构体优先队列

// 这里是小的优先，默认是大的优先
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n;
priority_queue<int,vector<int>,greater<int> >q;
int  main(){

q.push(3);
q.push(2);
int x=q.top();
cout<<x<<endl;
return 0;
}


// 对结构题进行优先队列 需要重载运算符
#include<cstdio>
#include<queue>
using namespace std;
struct node
{
    int x,y;
    bool operator < (const node & a) const
    {
        return x<a.x;
    }
}k;
priority_queue <node> q;
int main()
{
    k.x=10,k.y=100; q.push(k);
    k.x=12,k.y=60; q.push(k);
    k.x=14,k.y=40; q.push(k);
    k.x=6,k.y=80; q.push(k);
    k.x=8,k.y=20; q.push(k);
    while(!q.empty())
    {
        node m=q.top(); q.pop();
        printf("(%d,%d) ",m.x,m.y);
    }
}

set

// [天梯](https://www.patest.cn/contests/gplt/L2-014)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int  main(){
int n;
set<int>s;
cin>>n;
int t;
s.insert(0);
for(int i=0;i<n;i++){
    cin>>t;
    if(*s.rbegin()>t){
        s.erase(s.upper_bound(t));
    }
    s.insert(t);
}
cout<<s.size()-1<<endl;
return 0;
}

map

//  定义的三元组 用 map 判读是否 重复出现
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 25004
int k;
ll aa[N];

int c=0;


ll  gcd(ll a,ll b)
{
    return b==0?a:gcd(b,a%b);
}

    class Key
    {
    public:
        Key();
        Key(ll a,ll b,ll c);
        ll x,y,z;
        ~Key();

        bool operator <(const Key& key) const;
    };
    bool Key::operator <(const Key &key)  const
    {        if(this->x<key.x||this->x==key.x&&this->y<key.y||this->x==key.x&&this->y==key.y&&this->z<key.z)
            return true;
        else
            return false;
    }
    Key::Key()
    {
    }
    Key::Key(ll a,ll b,ll c)
    {
        x=a;y=b;z=c;
    }
    Key::~Key()
    {
    }
    map<Key,int>ma;
int main()
{
    cin>>k;
    ll x,y,z;
    cin>>x>>y>>z;
    ll a,c,b;

       for(int i=1;i<k;i++)
       {
          cin>>a>>b>>c;
          a=a-x;
          b-=y;c-=z;
          if(a!=0&&b!=0&&c!=0)
          {
         ll tem=gcd(a,b);
         tem=gcd(tem,c);
         a/=tem;b/=tem;c/=tem;
          }
         Key node;
         node.x=a;node.y=b;node.z=c;
       //  cout<<"dsaf "<<node.x<<" "<<node.y<<" "<<node.z<<endl;
         ma[node]=1;
          Key node2;
         node2.x=-a;node2.y=-b;node2.z=-c;
       //   cout<<node2.x<<" "<<node2.y<<" "<<node2.z<<endl;
         ma[node2]=1;
       }
     //  cout<<ma.size()<<endl;
      cout<<(ma.size()+1)/2<<endl;



    return 0;
}