OI

【做题笔记】2018.1.20

P1090合并果子

这题和上次只能合并相邻的合并石子不一样，直接贪心就行。然而对效率的要求比较高，于是被科普了一下什么是优先队列……

所以果子堆直接用堆维护了……（果子堆->堆）每一次取最小和次小的两个出来合并（最小的在堆顶，次小的在两个子节点中），维护堆即可。

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
#include<stdio.h>
#define inf 2147483647
int heap[20005]={0};
void sift(int k,int n){
    int i=k,j=2*i,f=0;
    int x=heap[k];
    while(!f&&j<=n){
        if(heap[j]>heap[j+1]&&j<n)
          j++;
        if(x<heap[j])f=1;
        else{
            heap[i]=heap[j];
            i=j;
            j=2*i;
        }
    }
    heap[i]=x;
}
void hp(int n){
    int i,t;
    for(i=n/2;i>=1;i--)
      sift(i,n);
}
int main(){
    int n,i,j;
    int s=0,t1,t2,t;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
      scanf("%d",&heap[i]);
    hp(n);
    for(i=1;i<n;i++){
        t1=heap[1];
        heap[1]=inf;
        if(heap[2]<heap[3])t=2;
        else t=3;
        t2=heap[t];
        heap[t]+=t1;
        s+=t1+t2;
        hp(n);
    }
    printf("%d",s);
    return 0;
}

P1181 数列分段Section I

这题和上一题就不是一个难度的……直接秒杀（

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    #include<stdio.h>
    int main(){
        int n,w,i,a[100005]={0};
        int s=1,t=0;
        scanf("%d%d",&n,&w);
        for(i=1;i<=n;i++)
          scanf("%d",&a[i]);
        for(i=1;i<=n;i++){
            t+=a[i];
            if(t>w){
                s++;
                t=a[i];
            }
        }
        printf("%d",s);
        return 0;
}