「D - Project Planning」&&「D. Productive Meeting」

D. Productive Meeting 题目描述：

n个人，每个人都有一个交谈次数，任意两个人都可以进行交谈，问如何安排可以使得交谈次数最大，输出最大值和每次交谈的人的id

思路：

肯定是贪心取最大的两个的人去交谈，然后记录输出即可

// Author: Chelsea
// 2021.09.28
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include "unordered_map"
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl 'n'
#define inf 0x3f3f3f3f
#define NMAX 500 + 50
#define MAX 1000000 + 50
//#define mod 998244353
#define lowbit(x) (x & (-x))
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define pd(n) printf("%dn", (n))
#define pdd(n,m) printf("%d %dn",n, m)
#define sddd(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)

typedef  long long ll;
typedef pair  pii;
typedef unsigned long long ull;
//不开longlong见祖宗!不看范围见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, x;
struct ran{
    int id, val;
    inline bool operator < (const ran &x)const{
           return val < x.val;
       }
};

void work()
{
    priority_queueq;
    sd(n);
    for(int i = 1; i <= n; ++i){
        sd(x);
        if(x != 0)q.push({i, x});
    }
    vectorv;
    vectornum;
    ll sum = 0;
    while (q.size() > 1) {
        ran a = q.top();q.pop();
        ran b = q.top();q.pop();
        --a.val;--b.val;
        ++sum;
        v.push_back(m_p(a.id, b.id));
        if(a.val != 0)q.push(a);
        if(b.val != 0)q.push(b);
    }
    cout<>tt;
    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
    }
    return 0;
}

D - Project Planning 题目描述：

和上个题差不多其实，上面是2个人，现在是k个人，k<=2e5,问最多能进行多少次交谈

思路：

1≤A_i≤10¹²,k<=2e5,数据巨大，没法直接模拟

所以我们考虑二分答案，也就是二分交谈次数

因为每次交谈都是不能有重复的人，所以check函数写的时候，求一个 s u m = ∑ 1 n m i n ( m i d , a [ i ] ) sum = sum_{1}^{n}{min(mid, a[i])} sum=∑1nmin(mid,a[i])，判断sum和mid * k的大小即可

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
using namespace std;

//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl 'n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 1000000007
#define lowbit(x) (x & (-x))
#define sz(s) (int)(s).size()
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%dn", (n))
#define pdd(n,m) printf("%d %dn",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef  long long ll;
typedef pair  pii;
typedef unsigned long long ull;
//不开longlong见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

//不改范围见祖宗!!!
#define MAX 1000000 + 50
ll n, m, k;
int x, y, z;
ll a, b, c;
string s, t;
ll tr[MAX];

bool judge(ll p){
    ll cnt = 0;
    for(int i = 1; i <= n; ++i){
        cnt += min(p, tr[i]);
    }
    return cnt >= k * p;
}

void work(){
    cin>>n;
    k = 2;
    ll sum = 0;
    for(int i = 1; i <= n; ++i){
        cin>>tr[i];
        sum += tr[i];
    }
    ll l = 0, r = sum / k;
    while (l <= r) {
        ll mid = (l + r) / 2;
        if(judge(mid))l = mid + 1;
        else r = mid - 1;
    }
    cout<>tt;
//    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
//    }
    return 0;
}

「D - Project Planning」&&「D. Productive Meeting」

C/C++/C#相关栏目本月热门文章