题意 给出n个pair （a,b） 把它放在线性序列上 1--n 上 使得 sum(a*(j-1)+b*(n-j)) 最小 思路 ：对式子进行合并 同类项 有： j*(a-b)+ (-a+
... .
题意 给出n个pair （a,b） 把它放在线性序列上 1--n 上 使得 sum(a*(j-1)+b*(n-j)) 最小
思路 ：对式子进行合并 同类项 有： j*(a-b)+ (-a+b*n) 可以发现 只和第一项有关 所以把a-b小的和大的j 结合即可
比赛的时候被B搞得心态爆炸就开始乱搞了 实际上已经试过a-b 了但是不知道为啥没有过样例 也怪自己不冷静 冷静一推也就是半分钟的事情
.
1 #include<bits/stdc++.h> 2 #define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++) 3 #define MS(arr,arr_value) memset(arr,arr_value,sizeof(arr)) 4 #define F first 5 #define S second 6 #define pii pair<int,int > 7 #define mkp make_pair 8 #define pb push_back 9 #define arr(zzz) array<ll,zzz>10 using namespace std;11 #define ll long long 12 const int maxn=3e5+5;13 const int inf=0x3f3f3f3f;14 vector<pii>v;15 int main(){16 int n;17 scanf("%d",&n);18 for(int i=0;i<n;i++){19 int a,b; 20 scanf("%d%d",&a,&b);21 v.pb(mkp(a,b));22 }23 sort(v.begin(),v.end(),[&](pii a,pii b)->bool{24 return a.F-a.S>b.F-b.S; 25 });26 ll ans=0;27 28 for(int i=0;i<n;i++){29 ans+=1ll*v[i].F*(i)+1ll*v[i].S*(n-i-1);30 }31 cout<<ans<<endl;32 33 return 0;34 }. View Code . . .. ...
