分析:并不是特别难的一道题,用到了贪心算法.

首先可以明确的一点是我们要尽量偷贡献最大的数据,要先满足每一个公司的贡献都大于等于K,以这个作为首要条件.那么我们可以先把每个快递公司的快递按照贡献从大到小排序,每次选贡献最大的,满足要求了就考虑下一个快递公司,如果过程中用超过了s个或者处理完后发现还有快递公司没有满足要求就输出无解.

上面只是满足了第一个要求,这时可能s个还没有用满,那么我们在按照贡献全体排一次序,看哪些没有用加上去就好了.

中途犯了一个很愚蠢的错误:直接把vis数组赋值为i,其实这是不对的,每一个vis应该对应快递的ID,而不是排序后的i!

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; int n, m, s, k;
long long ans,tot, cnt, sum, cnt2;
bool flag = false,can[]; struct node
{
long long e, t;
bool vis;
}a[]; bool cmp1(node a, node b)
{
if (a.e == b.e)
return a.t < b.t; //实际上是看谁的贡献最大
return a.e < b.e;
} bool cmp2(node a, node b)
{
return a.t < b.t;
} int main()
{
scanf("%d%d%d%d", &n, &m, &s, &k);
for (int i = ; i <= m; i++)
{
long long e, t;
scanf("%lld%lld", &e, &t);
if ( - t < )
{
a[++tot].e = e;
a[tot].t = - t;
}
}
sort(a + , a + + tot, cmp1);
if (a[tot].e < n)
{
printf("-23333333\n");
return ;
}
for (int i = ; i <= tot; i++)
{
if (can[a[i].e])
continue;
sum -= a[i].t;
cnt++;
a[i].vis = ;
if (cnt > s)
{
flag = ;
break;
}
if (sum >= k)
{
ans += sum;
sum = ;
can[a[i].e] = ;
}
}
for (int i = ; i <= n; i++)
if (!can[i])
{
flag = ;
break;
}
if (flag)
printf("-23333333\n");
else
{
sort(a + , a + tot + , cmp2);
for (int i = ; i <= tot; i++)
{
if (!a[i].vis)
{
cnt++;
ans -= a[i].t;
if (cnt == s)
break;
}
}
printf("%lld\n", ans);
} return ;
}

最新文章

  1. Cesium应用篇:3控件(2)BaseLayerPicker
  2. 解决ie8(及其以下)不支持getElementsByClassName的问题
  3. 获取ip的ip138.com
  4. HDU 1018 大数(求N!的位数/相加)
  5. POJ 1470 Closest Common Ancestors (最近公共祖先LCA 的离线算法Tarjan)
  6. (转)echo和print的区别
  7. Dockerfile制作sshd镜像
  8. mysql慢查优化总结
  9. java的CalssLoader
  10. GWAS文献解读:The stability of educational achievement across school years is largely explained by genetic factors
  11. 【Linux】grep命令
  12. 2082 : Only choose one
  13. Nginx 配置location root 转自https://blog.csdn.net/rofth/article/details/78581617
  14. Python之旅Day6 模块应用
  15. .Net 环境下比较各种数据库插入操作的性能
  16. C# 程序打包成安装项目
  17. Maven的多mirrors的配置
  18. centos下部署redis服务环境及其配置说明
  19. taro 微信小程序原生作用域获取
  20. R语言ggplot2 简介

热门文章

  1. MySQL索引使用以及优化
  2. LOJ#557. 「Antileaf&#39;s Round」你这衣服租来的吗(FHQ Treap+珂朵莉树)
  3. php 编译时 报错 configure: error: libXpm.(a|so) not found.
  4. Web前端汇总
  5. 对路径 obj 文件夹访问被拒绝
  6. Spring.Net学习笔记(7)-事务
  7. 神奇的Object.defineProperty
  8. 实例化Class类的5种方式
  9. 人人都能读懂的css3 3d小demo
  10. 禁止foreach循环使用remove/add----快速失败