一、成绩排序（排序、结构体排序）

任意门
这个竟然是华科的考研机试题。
题意就是将学生数据按成绩从低到高排序，如果成绩相同则按姓名字符的字典序排序，如果姓名的字典序也相同则按照学生的年龄从小到大排序。

如果能够用代码将这句话清晰准确的表达出来就可以了。

#include 
using namespace std;

struct st{
string name;
int age;
int grade;
bool operator <(const st &x)const{
    //将学生数据按成绩从低到高排序，如果成绩相同则按姓名字符的字典序排序，如果姓名的字典序也相同则按照学生的年龄从小到大排序
  
    if(grade==x.grade&&name!=x.name) return name<x.name;
    if(grade==x.grade&&name==x.name) return age<x.age;
    return grade<x.grade;
}
};
st stu[1010];
int main()
{
    int t;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        cin>>stu[i].name>>stu[i].age>>stu[i].grade;
    }
    sort(stu,stu+t);
    for(int i=0;i<t;i++)
        {
            cout<<stu[i].name<<" "<<stu[i].age<<" "<<stu[i].grade<<endl;
        }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

其中比较函数这样子写可能会更加的清晰简洁一点。

bool oprator<(const st&x)const
{
    if(grade!=x.grade)return grade<x.grade;
    if(name!=x.name)return name<x.name;
    return age<x.age;
}
1
2
3
4
5
6
7

二、倒计数（枚举、双指针）

任意门
题意：找一串数中，有没有给定数的“倒计数”，就是类似这样子的，给定k，然后这个数中，存在k,k-1,k-2,1这样的数，存在的话，有多少个呢？典型双指针

#include
using namespace std;

const int N=200010;

int n,m;
int q[N];

int main()
{
    int T;
    cin>>T;
    for(int cases=1;cases<=T;cases++)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            cin>>q[i];
        int res=0;
        for(int i=n;i>0;i--)
        {
            if(q[i]!=1)continue;
            int j=i-1;
            while(j>0&&q[j]==q[j+1]+1)j--;
            if(i-j>=m)res++;
            i=j+1;
        }
         printf("Case #%d: %d\n",cases,res);
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

三、G巴士计数（枚举、差分）

任意门

题意：就是给你每个巴士他是在哪个到哪个城市之间跑，然后要求你找一些巴士能够将他们全部覆盖。

#include
using namespace std;

const int N=5010;

int n,m;
int b[N];

int main()
{
    int T;
    cin>>T;
for(int cases=1;cases<=T;cases++)
 {
     memset(b,0,sizeof b);
     //每次差分数组都要清零
     scanf("%d",&n);
     for(int i=0;i<n;i++)
     {
         int l,r;
         scanf("%d%d",&l,&r);
         b[l]++,b[r+1]--;
     }
     for(int i=1;i<N;i++)
        b[i]+=b[i-1];
     cin>>m;
     printf("Case #%d: ",cases);
     while(m--)
     {
         int x;
         cin>>x;
         printf("%d ",b[x]);
     }
     puts("");
 }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

四、范围分区（思维题，贪心）

任意门
题意：就是将1~N当中的数分两堆，看他们的和的比例能不能满足X:Y，如果可以，就输出，不行就输出“Impossible”。

由于1~N之间的总和是确定的，所以比例确定了的话，我们就找是否能凑到这个数。他的前提条件有sn是否能够被x+y整除。

当然，这里有个结论就是可以用1~n之间的任意一个数表示出来（要满足前提条件）。
我们可以用数学归纳法来证明。

#include
using namespace std;

const int N=5010;

int n,x,y;
int b[N];

int main()
{
    int T;
    scanf("%d",&T);
for(int cases=1;cases<=T;cases++)
 {
     scanf("%d%d%d",&n,&x,&y);
     int sum=n*(n+1)/2;
     printf("Case #%d: ",cases);
   if(sum%(x+y))puts("IMPOSSIBLE");
   else{
        puts("POSSIBLE");
    vector<int>q;
   int a=sum/(x+y)*x;
   for(int i=n;i;i--)
    if(a>=i)
    {
        q.push_back(i);
        a-=i;
    }
    printf("%d\n",q.size());
    for(auto x:q)
        printf("%d ",x);
    puts("");
   }
 }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

五、坠落的蚂蚁（思维题、模拟）

任意门

题意：给你一个静止的蚂蚁，然后旁边的都是会动的，如果两个蚂蚁相碰，那么他们的速度互换。
我们可以找到这个蚂蚁左边和右边的蚂蚁个数，然后，左边的蚂蚁可以跟右边的蚂蚁抵消

#include
using namespace std;
#define x first
#define y second

typedef pair<int,int>PII;

int main()
{
    int n;
    cin>>n;
    vector<PII>q;
    int A;
    for(int i=0;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        if(!y)A=x;
        q.push_back({x,y});
    }
    sort(q.begin(),q.end());
    vector<int>l,r;
    for(auto& p:q)
    {
        if(!p.y||p.x<A&&p.y<0||p.x>A&&p.y>0)
            continue;//在其左边且朝左走或者在其右边且朝右走
        if(p.x<A)l.push_back(p.x);
        else r.push_back(p.x) ;
    }
    if(l.size()==r.size())cout<<"Cannot fall!"<<endl;
    else if(l.size()<r.size())cout<<r[l.size()]<<endl;
    else cout<<100-l[l.size()-1-r.size()]<<endl;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

六、破纪录者（模拟、枚举）

任意门
题意：很简单，就是记录下前面最大值，然后用自己的语言表达下就可以了。

#include
using namespace std;
const int N=200010;
int v[N];

int main()
{
   int T;
   cin>>T;
   int n,_max,res;
   for(int cases=1;cases<=T;cases++)
   {
       cin>>n;
       res=0;
       for(int i=0;i<n;i++)
        cin>>v[i];
       _max=v[0];
          for(int i=0;i<n;i++)
          {
              if(!i&&v[i]>v[i+1])res++;
              else if(i!=(n-1)&&v[i]>_max&&v[i]>v[i+1])res++;
             else  if(i==n-1&&v[i]>_max)res++;
             _max=max(v[i],_max);
          }
          printf("Case #%d: %d\n",cases,res);
   }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

if(v[i]>_max&&(i==n||q[i]>q[i+1]))
    res++;
1
2

这个代替核心函数会比较的好，比较简洁。

明年的目标院校也要考察算法，所以算法要好好学哇！不能再只是停留在基础的题目上了！