公元2023年7月20日20:10:排队接水,均分纸牌

发布时间 2023-07-20 20:26:49作者: 御坂16550号

今日AC二道贪心的题目

P1223 排队接水 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
int n;
double ttime;
struct p{//题目需输出编号,所以用一结构体
    int b,time;
}t[1005];
bool cmp(p x,p y){、、排序比较函数
    return x.time<y.time;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&t[i].time);
        t[i].b=i;
    }
    sort(t+1,t+n+1,cmp);//排序,很显然,等待时间越少的人先接水整体时间最少
    for(int i=1;i<=n;i++){
        printf("%d ",t[i].b);
        ttime+=t[i].time*(n-i);//累加,后面n-i个人都需等待t[i].time
    }
    printf("\n%.2lf",ttime/n);//保留两位小数输出
    return 0;
}

P1031 [NOIP2002 提高组] 均分纸牌 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

  这题我的方法是:

  1.算平均数。

  2.求每堆纸牌与平均数的关系(多1记为1,少1记为-1)。

  3.当q[y](第y堆纸牌与平均数的关系)不等于0时,q[y+1]=q[y+1]+q[y],移动次数加1。

 

#include<bits/stdc++.h>
using namespace std;
int n,a[105],ave,i,j,ans;
int main(){
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&a[i]);
        ave+=a[i];//统计平均数
    } 
    ave/=n;
    for(i=1;i<=n;i++){
        a[i]-=ave;//求每堆纸牌与平均数的关系
    }for(i=1;i<=n;i++){
        if(a[i]!=0){//为0(即到位了)跳过
            a[i+1]+=a[i];//移动
            a[i]=0;
            ans++;
        }
    }
    printf("%d",ans);
    return 0;
}