分类
OI

Luogu P1056 排座椅- NOIP 2008 PJ T2

0x00


题目:点此跳转
有一位好心的同学说他这道题不会做,给了我,让后我就被他的好心折磨了许久

0x01


一开始,我的思路是个暴力,让后……就没有然后了,手打了一下,算了一下O(3n^2)…… 如果是真考试,暴力应该能水上几分

0x02


于是我直接一个桶排,输入前面几个直接按顺序输出 WA50, 和sort没啥关系
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main(){
    int m,n,k,l,d;
    scanf("%d%d%d%d%d",&m,&n,&k,&l,&d);
    int ax[d],ay[d],bx[d],by[d],x[m+10],y[n+10];
    memset(x,0,sizeof(x));
    memset(y,0,sizeof(y));
    for(int i=0;i<d;i++){
        scanf("%d%d%d%d",&ax[i],&ay[i],&bx[i],&by[i]);
        if(ay[i]==by[i]) {
            int min;
            if(ax[i]<bx[i]) min=ax[i];
            else min=bx[i];
            x[min]++;
        }
        if(ax[i]==bx[i]) {
            int min;
            if(ay[i]<by[i]) min=ay[i];
            else min=by[i];
            y[min]++;
        }
    }
    int temp=0;
    for(int i=1;i<m+1;i++){
        if(temp==k) break;
        if(x[i]>0) {temp++;printf("%d ",i);}
    }
    printf("\n");
    temp=0;
    for(int i=1;i<n+1;i++){
        if(temp==l) break;
        if(y[i]>0) {temp++;printf("%d ",i);}
    }
}

0x03


直到我看到有一句话,叫做上课时交头接耳的学生的对数最少, 我去你妈最少,害得我多加了两个
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct FUCK{
    int x,min;
};
int cmp(FUCK a,FUCK b){
    return a.min>b.min;
}
int main(){
    int m,n,k,l,d;
    scanf("%d%d%d%d%d",&m,&n,&k,&l,&d);
    int ax[d],ay[d],bx[d],by[d];
    FUCK x[m+10],y[n+10];
    memset(x,0,sizeof(x));
    memset(y,0,sizeof(y));
    for(int i=0;i<d;i++){
        scanf("%d%d%d%d",&ax[i],&ay[i],&bx[i],&by[i]);
        if(ay[i]==by[i]) {
            int min;
            if(ax[i]<bx[i]) min=ax[i];
            else min=bx[i];
            x[min].min++;
            x[min].x=min;
        }
        if(ax[i]==bx[i]) {
            int min;
            if(ay[i]<by[i]) min=ay[i];
            else min=by[i];
            y[min].min++;
            y[min].x=min;
        }
    }
    sort(y,y+n+10,cmp);
    sort(x,x+m+10,cmp);
    int a[k+1];
    int b[l+1];
    int temp=0;
    for(int i=1;i<m+1;i++){
        if(temp==k) break;
        if(x[i].min>0) {temp++;a[i]=x[i].x;}
    }
    temp=0;
    for(int i=1;i<n+1;i++){
        if(temp==l) break;
        if(y[i].min>0) {temp++;b[i]=y[i].x;}
    }
    sort(a+1,a+k+1);
    sort(b+1,b+l+1);
    for(int i=1;i<=k;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
    for(int i=1;i<=l;i++){
        printf("%d ",b[i]);
    }
}
WA 0这很尴尬 问题
  • 数组未清0
  • 输出未排序

0x04


改了上述两个点,以下是ac代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct FUCK{
    int x,min;
};
int cmp(FUCK a,FUCK b){
    return a.min>b.min;
}
int main(){
    int m,n,k,l,d;
    scanf("%d%d%d%d%d",&m,&n,&k,&l,&d);
    int ax[d],ay[d],bx[d],by[d];
    FUCK x[m+10],y[n+10];
    memset(x,0,sizeof(x));
    memset(y,0,sizeof(y));
    for(int i=0;i<d;i++){
        scanf("%d%d%d%d",&ax[i],&ay[i],&bx[i],&by[i]);
        if(ay[i]==by[i]) {
            int min;
            if(ax[i]<bx[i]) min=ax[i];
            else min=bx[i];
            x[min].min++;
            x[min].x=min;
        }
        if(ax[i]==bx[i]) {
            int min;
            if(ay[i]<by[i]) min=ay[i];
            else min=by[i];
            y[min].min++;
            y[min].x=min;
        }
    }
    sort(y,y+n+10,cmp);
    sort(x,x+m+10,cmp);
    int a[k+1];
    int b[l+1];
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    int temp=0;
    for(int i=0;i<m+1;i++){
        if(temp==k) break;
        if(x[i].min>0) {temp++;a[i]=x[i].x;}
    }
    temp=0;
    for(int i=0;i<n+1;i++){
        if(temp==l) break;
        if(y[i].min>0) {temp++;b[i]=y[i].x;}
    }
    sort(a,a+k);
    sort(b,b+l);
    for(int i=0;i<k;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
    for(int i=0;i<l;i++){
        printf("%d ",b[i]);
    }
}

End


emmm……这题没啥技术含量,但是难想,这就比较尴尬 ]]>

发表评论

电子邮件地址不会被公开。 必填项已用*标注