Saruman's Army

首先对序列排序，然后逐个考虑覆盖，如果要覆盖当前的点，则标记点越靠后越好，所有向后找\(R\)，选择最靠后的标记，然后从标记点开始在向后找\(R\)也是被标记过的，直接跳过

#include <cstdio>
#include <algorithm>

using namespace std;

int read() {
    int x = 0, f = 1, ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
    if (ch == '-') f = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x * f;
}

const int N = 1005;
int n, r, a[N], cnt;

int main() {
    while (true) {
        r = read(), n = read(), cnt = 0;
        if (r == n && r == -1) return 0;
        for (int i = 1; i <= n; i++) a[i] = read();
        sort( a + 1 , a + 1 + n );
        for( int i = 1 , j , k ;  i <= n ; i = k ){
            cnt ++ ;
            for( j = i ; j <= n && a[j] <= a[i] + r ; j ++ );
            j --;
            for( k = j ; k <= n && a[k] <= a[j] + r ; k ++ );
        }
        printf("%d\n" , cnt );
    }
    return 0;
}

Fence Repair

#include <iostream>
#include <vector>
#include <queue>


using namespace std;

#define int long long

signed main() {
    int n , res = 0;
    cin >> n;
    priority_queue<int,vector<int> , greater<int> > q;
    for( int i = 1 , x ; i <= n ; i ++ )
        cin >> x , q.push(x);
    for( int a , b ; q.size() > 1; ){
        a = q.top() , q.pop();
        b = q.top() , q.pop();
        res += a + b , q.push( a + b );
    }
    cout << res << "\n";
    return 0;
}

Protecting the Flowers

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>


using namespace std;

#define int long long
struct node{
    int t , d;
};
bool cmp( node a , node b ){
    return a.t * b.d < b.t * a.d;
}

signed main() {
    int n , res = 0 , cnt = 0;
    cin >> n;
    vector<node> a(n);
    for( int i = 0 ; i < n ; i ++ )
        cin >> a[i].t >> a[i].d;
    sort( a.begin() , a.end() , cmp );
    for( int i = 0 ; i < n ; i ++ ){
        res += cnt * a[i].d , cnt += 2ll * a[i].t;
    }
    cout << res;
    return 0;
}

Yogurt factory

第i天生产酸奶的成本是c[i] = min( c[i] , c[i-1] + s )

求出每天最低酸奶成本后直接计算就好了。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>


using namespace std;

#define int long long

signed main() {
    int n , s , res = 0;
    cin >> n >> s;
    vector<int> c(n+1) , y( n+1 );
    for( int i = 1 ; i <= n ; i ++ )
        cin >> c[i] >> y[i];
    for( int i = 2 ; i <= n ; i ++ )
        c[i] = min( c[i] , c[i-1] + s );
    for( int i = 1 ; i <= n ; i ++ )
        res += c[i] * y[i];
    cout << res;
    return 0;
}

Cleaning Shifts

其实首先我们把所有的区间进行排序，首先安装左端点排序从小到大排序，如果左端点相同按照右端点从大到小排序。

排序后，我们在保证做端点可以衔接上的情况下尽可能大选择右端点即可。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct node {
    int l, r;
};

bool cmp(node a, node b) {
    if (a.l != b.l) return a.l < b.l;
    else return a.r > b.r;
}

int main() {
    int n, t;
    while (cin >> n >> t) {
        vector<node> a(n);
        for (int i = 0; i < n; i++)
            cin >> a[i].l >> a[i].r;
        sort(a.begin(), a.end(), cmp);
        if (a[0].l > 1) {
            cout << "-1\n";
            continue;
        }
        int res = 1, last = a[0].r, pos = last;
        for (int i = 1; i < n; i++) {
            if (a[i].l <= last + 1) { // 可以衔接上
                pos = max( pos , a[i].r);
                if (i == n - 1) {
                    if (pos > last) last = pos, res++;
                    break;
                }
            } else { // 衔接不上了
                if (pos > last) { // 有新增的覆盖
                    last = pos, res++;
                    if (last == t) break;
                    i--; // 当前区间还没有判断过
                } else {
                    res = -1;
                    break;// 无新增覆盖，说明之后的都衔接不上了
                }
            }
        }
        if (last != t) cout << "-1\n";
        else cout << res << "\n";
    }
    return 0;
}

Packets

优先放3,4,5,6然后用 2 去插空，剩余的 2 再占用新的盒子，最后用 1 去插空，剩余的 1 再占用新的盒子

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdio>


using namespace std;

int read() {
    int x = 0, f = 1, ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
    if (ch == '-') f = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x * f;
}

typedef pair<int, int> pii;

typedef pair<int, pii> piii;

int main() {
    int a, b, c, d, e, f;
    int A, B, cnt;
    while (true) {
        a = read(), b = read(), c = read(), d = read(), e = read(), f = read();
        if (a == 0 && b == 0 && c == 0 && d == 0 && e == 0 && f == 0)
            return 0;
        A = B = cnt = 0;
        cnt = (c + 3) / 4 + d + e + f;
        B = d * 5;
        if (c % 4 == 1) B += 5;
        else if (c % 4 == 2) B += 3;
        else if (c % 4 == 3) B += 1;
        cnt += (max(0, b - B) + 8) / 9;
        A = cnt * 36 - b * 4 - c * 9 - d * 16 - e * 25 - f * 36;
        cnt += (max(0, a - A) + 35) / 36;
        cout << cnt << "\n";
    }
    return 0;
}

Allowance

我们把所有的硬币按照面值排序，然后从大到小选择，在保证当前方案不超过C的情况下尽可能的多选面值大的。然后在从小到大选择，在保证可以大于等于C的情况下尽可能的选择面值小的。然后计算出当前方案可以使用的天数，如果无法构成，说明已经无法发放工资。

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdio>


using namespace std;

typedef long long ll;

typedef pair<ll, ll> pii;

int main() {
    ll n, c, res = 0;
    cin >> n >> c;
    vector<pii> coin;
    for (int i = 1, v, b; i <= n; i++) {
        cin >> v >> b;
        if (v >= c) res += b;
        else coin.push_back({v, b});
    }
    sort(coin.begin(), coin.end());

    while (true) {
        vector<int> used(coin.size(), 0);
        int cnt = c;
        for (int i = coin.size() - 1, t; i >= 0 && cnt > 0; i--) {
            t = min(cnt / coin[i].first, coin[i].second);
            used[i] = t, cnt -= t * coin[i].first;
        }

        for (int i = 0; cnt > 0 && i < coin.size(); i++)
            while (cnt > 0 && used[i] < coin[i].second)
                used[i]++, cnt -= coin[i].first;
        if( cnt > 0 ) break;
        ll ans = 1e18;
        for( int i = 0 ; i < coin.size() ; i ++ )
            if( used[i] > 0 ) ans = min( ans , coin[i].second / used[i] );
        res += ans;
        for( int i = 0 ; i < coin.size() ; i ++ )
            coin[i].second -= ans * used[i];
    }
    cout << res << "\n";
    return 0;
}

Stripies

这种一眼贪心，其实最简单的方法就是两种贪心策略都试就好。

证明其实也不难，要把\(a,b,c\)合成\(d\)

显然这里，\(d>0\)恒成立，所以\(d\)和\(\frac{d^2}{8}\)增减性相同，要使得\(d\)最小，则\(a,b\)是较大的两个值

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <cmath>


using namespace std;

typedef long long ll;

int main() {
    priority_queue<double> q;
    int n;
    cin >> n;
    for (double x; n; n--)
        cin >> x, q.push(x);
    for (double a, b, c; q.size() > 1;) {
        a = q.top(), q.pop();
        b = q.top(), q.pop();
        c = 2.0 * sqrt(a * b) , q.push(c);
    }
    printf("%.3f" , q.top() );
    return 0;
}

本栏目推荐文章
• 2023年度总结
• spring与设计模式之三代理模式
• 深入理解spring框架：剖析多线程模式下数据库连接
• CSP-J/S 2023 游记
• Libevent [补档-2023-08-29]
• 本地套接字 [补档-2023-07-24]
• UDP通信 [补档-2023-07-22]
• 多路io复用Select [补档-2023-07-16]
• 多路io复用pool [补档-2023-07-19]
• 多路io复用epoll [补档-2023-07-20]

Spring 2023 SMUspring 2023 smu autumn round 2023 smu smu spring hello 2023 project1 project spring 2023 project2 project spring 2023 难度 答案spring 2023 project3 project spring 2023 contest spring round 2023 project0 project spring 2023