今日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;
}