nowcoder牛客wannafly挑战赛20

A---染色

签到题，设最终颜色为x，一次操作就需要把一个不是x的点变为x，所以最终颜色为x时需要操作总结点个数-颜色为x的节点个数，然后枚举所有颜色就行了

 #include <iostream>

 #include <string.h>

 #include <cstdio>

 #include <vector>

 #include <map>

 #include <math.h>

 #include <string>

 #include <algorithm>

 #include <time.h>

 #define SIGMA_SIZE 26

 #define lson rt<<1

 #define rson rt<<1|1

 #define lowbit(x) (x&-x)

 #define foe(i, a, b) for(int i=a; i<=b; i++)

 #define fo(i, a, b) for(int i = a; i < b; i++);

 #pragma warning ( disable : 4996 )

 using namespace std;

 typedef long long LL;

 inline LL LMax(LL a,LL b)      { return a>b?a:b; }

 inline LL LMin(LL a,LL b)      { return a>b?b:a; }

 inline LL lgcd( LL a, LL b ) { return b==?a:lgcd(b,a%b); }

 inline LL llcm( LL a, LL b ) { return a/lgcd(a,b)*b; }  //a*b = gcd*lcm

 inline int Max(int a,int b)    { return a>b?a:b; }

 inline int Min(int a,int b)    { return a>b?b:a; }

 inline int gcd( int a, int b ) { return b==?a:gcd(b,a%b); }

 inline int lcm( int a, int b ) { return a/gcd(a,b)*b; }  //a*b = gcd*lcm

 const LL INF = 0x3f3f3f3f3f3f3f3f;

 const LL mod  = ;

 const double eps = 1e-;

 const int inf  = 0x3f3f3f3f;

 const int maxk = 1e6+;

 const int maxn = 1e5+;

 int N, ct;

 int cnt[maxn];

 LL num[maxn];

 LL all;

 struct col {

     int id;

     LL val;

     col() {}

 }color[maxn];

 bool cmp(const col& a, const col& b)

 {

     return a.val < b.val;

 }

 void read()

 {

     memset(cnt, , sizeof(cnt));

     memset(num, , sizeof(num));

     all = ;

     foe(i, , N)

     {

         scanf("%lld", &color[i].val);

         all += color[i].val;

         color[i].id = i;

     }

     sort(color+, color++N, cmp);

     int x, y;

     foe(i, , N-)

     {

         scanf("%d %d", &x, &y);

     }

 }

 int main()

 {

     while (~scanf("%d", &N))

     {

         read();

         LL tmp = color[].val;

         num[] = color[].val;

         cnt[] = ;

         ct = ;

         foe(i, , N)

         {

             if (color[i].val == tmp)

             {

                 cnt[ct]++;

                 continue;

             }

             tmp = color[i].val;

             num[++ct] = tmp;

             cnt[ct] = ;

         }

         LL mmin = INF;

         foe(i, , ct)

         {

             tmp = all;

             tmp -= num[i]*cnt[i];

             if (tmp >= mmin) continue;

             tmp += (N-cnt[i])*num[i];

             mmin = LMin(tmp, mmin);

         }

         printf("%lld\n", mmin);

     }

     return ;

 }

B---背包

我觉得这道题有点问题...先按价值排个序，然后考虑中位数两边最小的体积是多少呢，用优先队列从1~N扫一遍，再从N~1扫一遍，就可以记录下每个点往左和往右的所有物品中，取体积最小的M/2个物品的体积总和是多少，分别记为sum1[i],sum2[i]，然后分奇偶讨论一下就行了（还是觉得数据有点问题，）

 #include <iostream>

 #include <string.h>

 #include <cstdio>

 #include <vector>

 #include <map>

 #include <queue>

 #include <math.h>

 #include <string>

 #include <algorithm>

 #include <time.h>

 #define SIGMA_SIZE 26

 #define lson rt<<1

 #define rson rt<<1|1

 #define lowbit(x) (x&-x)

 #define foe(i, a, b) for(int i=a; i<=b; i++)

 #define fo(i, a, b) for(int i = a; i < b; i++);

 #pragma warning ( disable : 4996 )

 using namespace std;

 typedef long long LL;

 inline LL LMax(LL a, LL b) { return a>b ? a : b; }

 inline LL LMin(LL a, LL b) { return a>b ? b : a; }

 inline LL lgcd(LL a, LL b) { return b ==  ? a : lgcd(b, a%b); }

 inline LL llcm(LL a, LL b) { return a / lgcd(a, b)*b; }  //a*b = gcd*lcm

 inline int Max(int a, int b) { return a>b ? a : b; }

 inline int Min(int a, int b) { return a>b ? b : a; }

 inline int gcd(int a, int b) { return b ==  ? a : gcd(b, a%b); }

 inline int lcm(int a, int b) { return a / gcd(a, b)*b; }  //a*b = gcd*lcm

 const LL INF = 0x3f3f3f3f3f3f3f3f;

 const LL mod = ;

 const double eps = 1e-;

 const int inf = 0x3f3f3f3f;

 const int maxk = 1e6 + ;

 const int maxn = 1e5 + ;

 //优先队列默认从大到排列

 priority_queue<LL> qq;

 int V, N, M;

 LL sum;

 LL sum1[maxn], sum2[maxn];

 struct node {

     LL val, cost;

 }pp[maxn];

 bool cmp(const node& a, const node& b)

 {

     return a.val == b.val ? a.cost<b.cost : a.val<b.val;

 }

 void init()

 {

     foe(i, , N)

         scanf("%lld %lld", &pp[i].val, &pp[i].cost);

     sort(pp + , pp +  + N, cmp);

 }

 void solve(int i, int mid, LL ss[])

 {

     ss[i] = sum;

     sum += pp[i].cost;

     qq.push(pp[i].cost);

     if (qq.size() > mid) {

         sum -= qq.top();

         qq.pop();

     }

 }

 int main()

 {

     cin >> V >> N >> M;

     init();

     sum = ;

     int mid = M / ;

     //正向扫一遍

     for (int i = ; i <= N; i++)

         solve(i, mid, sum1);

     sum = ; while (!qq.empty()) qq.pop();

     //反向扫一遍

     for (int i = N; i >= ; i--)

         solve(i, mid, sum2);

     if (M % )

     {

         for (int i = N - mid; i >= mid + ; i--)

             if (sum1[i] + sum2[i] + pp[i].cost <= V)

             {

                 printf("%lld\n", pp[i].val);

                 break;

             }

     }

     else

     {

         for (int i = N - mid + ; i >= mid; i--)

             if (sum1[i] + sum2[i - ] <= V)

             {

                 printf("%lld\n", (pp[i].val + pp[i - ].val) / );

                 break;

             }

     }

     return ;

 }

巴特西

nowcoder牛客wannafly挑战赛20

最新文章

热门文章