分类目录归档：贪心

洛谷 智力大冲浪

发表评论

题号：1230
一开始想排完序之后直接从前到后由时间1到时间n依次安排，这样做是不对的。
完全可以从一个任务的截止时间开始从后往前安排，哪里有空缺位置就放在那里。
一开始的想法忽略了其他任务也可以放在前面。（说的不太清楚）

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
#include<iostream>
#include<algorithm>
using namespace std;
int m, n;
struct s{
    int t;
    int w;
    bool operator < (s & s1){
        if (w != s1.w)return w>s1.w;
        else return t < s1.t;
    }
}arr[505];
bool occupied[505];
int main(){
    ios::sync_with_stdio(false);
    cin >> m >> n;
    for (int i = 1; i <= n; i++){
        cin >> arr[i].t;
    }
    for (int i = 1; i <= n; i++){
        cin >> arr[i].w;
    }
    sort(arr + 1, arr + n + 1);
    for (int i = 1; i <= n; i++){
        if (!occupied[arr[i].t])occupied[arr[i].t] = true;
        else{
            bool flag = false;
            for (int j = arr[i].t - 1; j >= 1;j--){
                if (!occupied[j]){
                    occupied[j] = true;
                    flag = true;
                    break;
                }
            }
            if (!flag)m -= arr[i].w;
        }
    }
    cout << m;
}

洛谷 均分纸牌

发表评论

题号：1031

参考某大神的题解，受了点启发，想了个思路，有可能是和别人是重的，但我还是说一下，毕竟别人的不是特别好懂。

首先读入数据，计算出每个堆上应有的平均分配之后的值。既然最终的目的是要求所有堆都统一为平均值，那我就先不管后面的，先把现在的当前堆管好再说。利用贪心的想法，从左向右遍历，当前堆上的牌数小于平均值就从右面一个堆往过要，大于平均值就把多的全部扔给右面一个堆。过程中有可能出现负数，但是最后肯定是会回到正常的状态。每个堆上的牌至多主动挪出一次，是符合题目要求的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;
int main(){
    int n,arr[101],sum=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        sum+=arr[i];
    }
    int avg=sum/n;
    int step=0;
    for(int i=1;i<n;i++){
        if(arr[i]<avg){
            step++;
            arr[i+1]-=avg-arr[i];
        }else if(arr[i]>avg){
            step++;
            arr[i+1]+=arr[i]-avg;
        }
    }
    cout<<step;
}

THU2017spring 1-4 Hospital 题解

发表评论

THU2017spring 1-4 Hospital

描述

有n个村落分布在一条公路的沿线，为方便村民们就医，现打算在公路沿线修建一所医院。

由于各村落人数、年龄分布不同等原因，每个村落对医院的需求程度也不同。这里需求程度以一个非负的权值w表示：w越大，就医需求越大。对于一个选址方案，Σwi*di作为衡量其合理性的指标，其中wi和di分别表示第i个村落的权值和距离医院的距离，该指标越小，对应的选址就越优。请给出医院修建的最优位置。

输入

共n+1行。

第一行包含一个整数n；

以下共n行，每行包含两个整数：第一个为对应村落的一维坐标xi，第二个为对应村落的权值wi。

输出

共两行。

第一行为医院的最优坐标。

第二行为对应的最小权值，即医院选择最优坐标时的Σwi*di。

注意，如果有多个坐标权值均为最小值，请给出这些坐标中的最小者。

输入样例

3
3 5
7 11
5 6

输出样例

5
32

限制

1 <= n <= 300,000

村落的地址坐标是[0, 32767]的整数。

村落的权值是[1, 10^8]的整数。

时间：1 sec

空间：256 MB

提示

一级提示

● 可以在预处理时将坐标相同的村落合并。

二级提示

● 考虑医院选址向左（或向右）移动一个单位对Σwi*di的影响何时为正、何时为负。

● 注意你的程序是否能正确处理“有多个坐标权值均为最小值”的情况。

● 虽然最终选址坐标在int范围内，但计算Σwi*di的中间过程不一定在int范围内；可以使用long long，其表示的范围是[-2^63, 2^63)。

我也实在不知道该怎么做，参考twd2的做法什么“加权中位数”，胡作吧。最后80分。。

继续阅读 →