百度验证网站,建筑网名,电子商务网站建设预算表,手风琴网站模板题目描述 Description阿明是一名推销员#xff0c;他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同#xff0c;出口与入口是同一个#xff0c;街道的一侧是围墙#xff0c;另一侧是住户。螺丝街一共有N家住户#xff0c;第i家住户到入口的距离为Si米。由于同一栋房… 题目描述 Description 阿明是一名推销员他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同出口与入口是同一个街道的一侧是围墙另一侧是住户。螺丝街一共有N家住户第i家住户到入口的距离为Si米。由于同一栋房子里可以有多家住户所以可能有多家住户与入口的距离相等。阿明会从入口进入依次向螺丝街的X家住户推销产品然后再原路走出去。阿明每走1米就会积累1点疲劳值向第i家住户推销产品会积累Ai点疲劳值。阿明是工作狂他想知道对于不同的X在不走多余的路的前提下他最多可以积累多少点疲劳值。 输入描述 Input Description 第一行有一个正整数N表示螺丝街住户的数量。接下来的一行有N个正整数其中第i个整数Si表示第i家住户到入口的距离。数据保证S1≤S2≤…≤Sn10^8。接下来的一行有N个正整数其中第i个整数Ai表示向第i户住户推销产品会积累的疲劳值。数据保证Ai10^3。 输出描述 Output Description 输出N行每行一个正整数第i行整数表示当Xi时阿明最多积累的疲劳值。 样例输入 Sample Input 【样例1】51 2 3 4 51 2 3 4 5【样例2】51 2 2 4 55 4 3 4 1 样例输出 Sample Output 【样例1】1519222425【样例2】1217212427 数据范围及提示 Data Size Hint 1≤N≤100000注请用 scanf 输入。 /*刚开始想了一个贪心思路不知道对不对然而真的就对了只不过是O(n^2)的TLE然后用优先队列优化就过了。贪心思路首先我们明确找前i个住户一定是在i-1的基础上找的具体方法是记录当前我们最远找到的村庄位置now因为当你往回找和往前找时走的路程是不同的对于now来说我们有两种决策一种是向上找一种是向下找找到最大值加入ans这样是O(n^2)的方法。然而我们发现向上找的部分会随now的变大而逐渐不浪费时间向下找的部分则会重复找很多次所以我们搞一个优先队列再记录一个当前最远的入队元素位置from每次当我们更新now时就把from1到now内的元素放入优先队列这样我们在下一次向下找的时候就不用再循环一遍而是直接从优先队列中取头元素就好了。
*/
#includecstdio
#includeiostream
#includequeue
#includealgorithm
#define M 100010
using namespace std;
int n,ans;
struct node
{int v,pos;bool operator (node x)const{return vx.v;}
};node a[M],b;
priority_queuenode q;
int main()
{scanf(%d,n);for(int i1;in;i)scanf(%d,a[i].pos);for(int i1;in;i)scanf(%d,a[i].v);b.v0;b.pos0;q.push(b);int now0,from;for(int i1;in;i){bq.top();int mxb.v,p0;for(int jnow1;jn;j)if((a[j].pos-a[now].pos)*2a[j].vmx){mx(a[j].pos-a[now].pos)*2a[j].v;pj;}if(p){b.posp;b.vmx;fromnow;nowp;q.push(b);for(int jfrom1;jnow;j)q.push(a[j]);}node bq.top();ansb.v;q.pop();printf(%d\n,ans);}return 0;
} View Code 转载于:https://www.cnblogs.com/harden/p/5811386.html
