复赛2:插入排序

洛谷P7910

暴力解法: 76分

 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
39
40
41
42
43
44
45
#include <iostream>
#include <algorithm>
using namespace std;

struct node{
    int id,num;
}a[8010];

bool cmp(node a, node b){
    if(a.num == b.num)return a.id<b.id;
     else return a.num<b.num;
}
int main(){
    int n,q,op,u,v;
    cin>>n>>q;
    for (int i = 1; i <=n; i++){
        cin>>a[i].num;
        a[i].id=i;
    }
    sort(a+1,a+1+n,cmp);
    while(q--){
        cin>>op;
        if(op==1){ //操作1修改
              cin>>u>>v;
              for (int i = 1; i <=n; i++){
                if(a[i].id==u){
                    a[i].num=v;
                    break;
                }
              }
              sort(a+1,a+1+n,cmp);
        }else {
             cin>>u;
             for (int i = 1; i <=n; i++){
                 if(a[i].id==u){
                    cout<<i<<endl;
                    break;
                 }
             }
             

        }
    }
    
}

完美解法:

 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**************************************************************** 
 * Description: 
 * Author: Alex Li
 * Date: 2023-10-15 20:21:59
 * LastEditTime: 2023-10-15 20:47:23
****************************************************************/
#include <iostream>
#include <algorithm>
using namespace std;

struct node{
    int id,num;
}a[8010];

int b[8010];
int n;
bool cmp(node a, node b){
    if(a.num == b.num)return a.id<b.id;
     else return a.num<b.num;
}

void change(int pos){
    while(pos>1){
        if(a[pos].num>a[pos-1].num)break;
        if(a[pos].num==a[pos-1].num&& a[pos].id>a[pos-1].id)break;
        swap(a[pos],a[pos-1]);
        b[a[pos].id]=pos;
        pos--;
    }
    while(pos<n){
         if(a[pos].num<a[pos+1].num)break;
        if(a[pos].num==a[pos+1].num&& a[pos].id<a[pos+1].id)break;
        swap(a[pos],a[pos+1]);
        b[a[pos].id]=pos;
        pos++;
    }
    b[a[pos].id]=pos;
}
int main(){
    int q,op,u,v;
    cin>>n>>q;
    for (int i = 1; i <=n; i++){
        cin>>a[i].num;
        a[i].id=i;
    }
    sort(a+1,a+1+n,cmp);
    for (int i =1; i <=n; i++){
        b[a[i].id]=i;
    }
    
    while(q--){
        cin>>op;
        if(op==1){ //操作1修改
              cin>>u>>v;
            a[b[u]].num=v;
            change(b[u]);
        }else {
             cin>>u;
           cout<<b[u]<<endl;
        }
    }
    
}
Scroll to Top