try3.cpp

poj 3598 new new hen rong yi tle

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#define MAXN 100000
using namespace std;

struct Speed
{
    int v;
    int w;
    bool operator<(const Speed &s) const
    {
        if((v>s.v)||((v==s.v)&&(w>s.w)))
        {
            return true;
        }
        else
        {
            return false;
        }
    }
}speed[MAXN+1];

vector<Speed> kart[MAXN+1];
int m,n;

int binary_search(int w)
{
    int low,high,mid;
    low=1;
    high=m;
    do
    {
        mid=(low+high)>>1;
        if(kart[mid][0].w>=w)
        {
            low=mid+1;
        }
        else
        {
            high=mid;
        }
    }while(low<high);
    return high;
}

int main()
{
    int i,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d %d",&speed[i].v,&speed[i].w);
    }
    sort(speed+1,speed+n+1);                          //sort   不明白
    m=0;
    kart[++m].push_back(speed[1]);                        //  不懂之处
    for(i=2;i<=n;i++)
    {
        if(kart[m][0].w>=speed[i].w)
        {
            kart[++m].push_back(speed[i]);                       //同
        }
        else
        {
            kart[binary_search(speed[i].w)].push_back(speed[i]);     //push_back
        }   
    }
    for(i=1;i<=m;i++)
    {
        printf("%d:",kart[i].size());
        for(j=kart[i].size()-1;j>=0;j--)
        {
            printf(" (%d,%d)",kart[i][j].v,kart[i][j].w);
        }
        printf("\n");
    }
    return 0;
}