[Codeforces] 477 D. Resource Distribution

題目連結:http://codeforces.com/contest/967/problem/D
  只有兩個要處理的服務,所以就會猜是某種單調性或前綴或後綴之類的,通常是先O(N)或O(nlgn)之類的預處理前或後綴去處理其中一個,再O(N)或O(nlgn)處理剩下的之類的吧?


#include<bits/stdc++.h>
#define debug(a) cout << #a << " = " << a << endl;
#define pb push_back
#define int long long
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef pair<int,int> pi;
int n,x1,x2;
pi c[300009];
vector<int> ans1,ans2;
signed main()
{
    cin >> n >> x1 >> x2;
    for(int i = 0; i < n; i++) 
    {
        cin >> c[i].first;
        c[i].second = i;
    }
    sort(c,c+n);
    int maxu = 1e9; bool ok = 0; int dd;
    for(int i = n-1; i >= 0; i--)
    {
        int ddd = x2/c[i].first;
        if(x2%c[i].first != 0) ddd += 1;
        if(n-i >= ddd) 
        {
            dd = ddd;
            maxu = i;
            ok = 1;
            break;
        }
    }
    for(int i = 0; i < n && ok; i++)
    {
        int kk = x1/c[i].first;
        if(x1%c[i].first != 0) kk += 1;
        if(kk+i >= n) continue;
        if(kk+i <= maxu)
        {
            cout << "Yes" << endl;
            cout << kk << " " << dd << endl;
            for(int j = i; j < kk+i; j++) ans1.pb(c[j].second);
            sort(all(ans1));
            for(int j = maxu; j < n; j++) ans2.pb(c[j].second);
            sort(all(ans2));
            for(auto j:ans1) cout << j+1 << " "; cout << endl;
            for(auto j:ans2) cout << j+1 << " "; cout << endl;
            return 0;
        }
    }
    swap(x1,x2);
    ok = 0;
    for(int i = n-1; i >= 0; i--)
    {
        int ddd = x2/c[i].first;
        if(x2%c[i].first != 0) ddd += 1;
        if(n-i >= ddd) 
        {
            dd = ddd;
            maxu = i;
            ok = 1;
            break;
        }
    }
    for(int i = 0; i < n && ok; i++)
    {
        int kk = x1/c[i].first;
        if(x1%c[i].first != 0) kk += 1;
        if(kk+i >= n) continue;
        if(kk+i <= maxu)
        {
            cout << "Yes" << endl;
            cout << dd << " " << kk << endl;
            for(int j = i; j < kk+i; j++) ans1.pb(c[j].second);
            sort(all(ans1));
            for(int j = maxu; j < n; j++) ans2.pb(c[j].second);
            sort(all(ans2));
            for(auto j:ans2) cout << j+1 << " "; cout << endl;
            for(auto j:ans1) cout << j+1 << " "; cout << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}

留言

這個網誌中的熱門文章

Shellshock.io從入門到上手(針對單狙)(沒有圖片、影片版本)

[TIOJ] 1007燈泡問題