題目描述

情人節又到了，又到了一年一度發紅包的時間。經大家研究決定，今年讓奎奎自愿發紅包。
俱樂部有n個人(0<n<100000)，每個人都有一個單身值v[i]與親密度t[i](0≤v[i]≤10000,0≤t[i]≤10000)，單身值越大的人，在情人節的時候就越羨慕奎奎，奎奎就需要給他更大的紅包來安慰他。 由于一個寒假沒有見到奎奎，領紅包的時候大家都想跟奎奎py，花費時間t[i]，先py后給紅包噢。
大家都厭倦了等待，如果一個人等了時間t，那么奎奎發給他的紅包大小就是v[i]·t。
但是奎奎還要和女朋友去快樂，想要花最少的錢來滿足大家。
請你幫他計算最少需要發多少錢的紅包。

輸入

第一行一個整數n。接下來n行，每行兩個數v[i]和t[i]。

輸出

一個整數表示答案。

樣例輸入 Copy

4 1 4 2 3 3 2 4 1

樣例輸出 Copy

35

---

題目分析：簽到題貪心。。請教的ybl大佬，我真的太弱了

每個人都有兩個屬性 v[ i?] 和 t[ i ]，考慮前后兩個人，x 和 y 的相對位置：

如果 x 在前 y 在后：v[ x ] * t[ x ] + v[ y ] * ( t[ x ] + t[ y ] ) =?v[ x ] * t[ x ] + v[ y ] * t[ x ] + v[ y ] * t[ y ]

如果 y 在前 x 在后：v[ y ] * t[ y ] + v[ x ] * ( t[ x ] + t[ y ] ) = v[ y ] * t[ y ] + v[ x?] * t[ x ] + v[ x ] * t[ y ]

也就是說，當?v[ x ] * t[ x ] + v[ y ] * t[ x ] + v[ y ] * t[ y ] <?v[ y ] * t[ y ] + v[ x?] * t[ x ] + v[ x ] * t[ y ] 時，x 在前

可能這樣看著還是有點亂，約分一下： v[ y ] * t[ x ] < v[ x ] * t[ y ] 時，x 在前

然后排序一下就好了

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;struct Node {int v,t;void input(){scanf("%d%d",&v,&t);}bool operator<(const Node& a)const{return a.v*t<a.t*v;} }a[N];int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<=n;i++)a[i].input();sort(a+1,a+1+n);LL ans=0,time=0;for(int i=1;i<=n;i++){time+=a[i].t;ans+=time*a[i].v;}printf("%lld\n",ans);return 0; }

?

總結

以上是生活随笔為你收集整理的中石油训练赛 - 奎奎发红包(贪心)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。