JZOJ-senior-5955. 【NOIP2018模拟11.7A组】strategy
Time Limits: 1000 ms Memory Limits: 262144 KB
Description
Input
Output
一行 n 个整数,第 i 个数表示和第 i 个敌人结盟时的最小代价。
Sample Input
4 2
1 5
2 3
2 4
3 5
Sample Output
8 8 7 6
Data Constraint
对于 70% 的数据,保证 n ≤ 400。
对于 100% 的数据,保证 n ≤ 4000。
Solution
贪心,强制全选右,记为 ,右边减左边,从大到小排个序
前 大而且不为 ,编号不为 的数加起来,记为
题解的 是什么鬼东西……
由于 也可以过,下面代码就没有优化,实际上可以用前缀和做到
Code
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cctype>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
#define P(c) putchar(c)
#define ll long long
using namespace std;
const int N=4e3+5;
int n,k,b[N];
struct node{int z,id;}a[N];
inline void read(int &n)
{
int x=0,w=0; char ch=0;
while(!isdigit(ch)) w|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
n=w?-x:x;
}
inline void write(ll x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
bool cmp(node x,node y)
{
return x.z>y.z;
}
int main()
{
freopen("strategy.in","r",stdin);
freopen("strategy.out","w",stdout);
read(n),read(k); ll sum=0;
fo(i,1,n)
{
int x,y;
read(x),read(y);
b[i]=y,sum=(ll)sum+(ll)y;
a[i].z=y-x,a[i].id=i;
}
sort(a+1,a+1+n,cmp);
fo(i,1,n)
{
ll ans=sum-(ll)b[i];
int c=0,j=1;
while(c<k)
{
if(a[j].z<0) break;
if(a[j].id!=i) ans-=a[j].z,++c;
++j;
}
write(ans),P(' ');
}
}