精华内容
下载资源
问答
  • 最优服务次序问题

    2018-04-06 20:59:15
    最优服务次序问题

    最优服务次序问题


    问题描述
    设有n个顾客同时等待一项服务。顾客i所需要的服务时间为ti,1 <= i <= n。
    应如何安排顾客的服务次序,才能使平均等待时间最短?
    平均等待时间是n个顾客等待服务时间的总和除以n。

    示例
    input:
    10
    56 12 1 99 1000 234 33 55 99 812

    output:
    532.00

    分析
    贪心算法。

    要使n个顾客平均等待时间最小,应该让n个顾客等待服务时间之和最小。
    要实现等待服务时间和最小,应该优先安排ti值小的顾客进行服务。

    以示例来分析:
    (1)未按照ti值小的顾客优先进行服务
    第一个顾客需要的服务时间为56,那么第一个顾客以及他后面的每一个顾客都需要56的时间(这个题好像把顾客自己需要的服务时间也计入了等待服务时间);再到第二个顾客,第三个顾客,依此类推……这样得到的结果肯定不是平均服务时间最小的。

    (2)按照ti值小的顾客优先进行服务
    按照ti值小的顾客优先进行服务的话,那么第一个进行服务的顾客需要的时间是1,他以及他后面的每一个顾客都只需要1的时间……按照这种贪心的策略,我们可以得到平均服务时间最小的结果。

    #include <stdio.h>
    #include <algorithm>
    using namespace std;
    
    int g[1000005];
    
    int
    main() {
        int n, i, ans;
        double ave;
    
        scanf("%d", &n);
        for( i = 0; i < n; i++ ) {
            scanf("%d", &g[i]);
        }
        sort(g, g + n);
        ans = 0;
        for( i = 0; i < n; i++ ) {
            ans += (g[i] * (n - i));
        }
        ave = 1.0 * ans / n;
        printf("%f\n", ave);
    
        return 0;
    }
    展开全文
  • 最优服务次序问题及多处最优服务次序问题一、最优服务次序问题题目输入输出代码注意事项二、多处最优服务次序问题题目输入输出代码 一、最优服务次序问题 题目 问题描述:设有n个顾客同时等待一项服务,顾客i需要...



    一、最优服务次序问题

    题目

    问题描述:设有n个顾客同时等待一项服务,顾客i需要的服务时间为ti,(1<=i<=n)。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?(平均等待时间是n个顾客等待服务时间总和除以n)

    输入

    第一行为一个正整数n,表示有n个顾客
    第二行为n个正整数,表示n个顾客需要的服务时间

    输出

    最小平均等待时间

    代码

    #include<stdio.h>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define MAXN 100000
    
    int n;//n个顾客
    double arr[MAXN];
    
    void input(){
    	scanf("%d",&n);
    	for(int i = 0;i < n;i++){
    		scanf("%lf",&arr[i]);
    	}
    }
    
    double calculate(){
    	int i = 0;
    	double sum = 0;//总等待时间
    	double temp = 0;
    	for(i = 0;i < n;i++){
    		temp += arr[i];
    		sum += temp;
    	}
    	return sum/n;
    }
    
    int main(){
    	input();
    	sort(arr,arr + n);
    	printf("%.2f\n",calculate());
    	return 0;
    }
    
    

    注意事项

    这一题和下一题的等待时间,都包括了自己本身的服务时间
    例如:
    第一个人的等待时间 = 0(因为它前面没有人,不需要等)+ 自身所需服务时间
    第n个人的等待时间 = 前面所有人的等待时间 + 自身所需服务时间



    二、多处最优服务次序问题

    题目

    问题描述:设有n个顾客同时等待一项服务,顾客i需要的服务时间为ti,(1<=i<=n)。共有s处可以提供此项服务。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?

    输入

    第一行为两个正整数n和s
    第二行为n个正整数,表示n个顾客需要的服务时间

    输出

    最小平均等待时间。

    代码

    #include<bits/stdc++.h>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    #define MAXN 100000
    
    int n,s;//n个顾客,s处可提供此项服务 
    int arrCustomer[MAXN];//存储用户所需服务时间 
    int arrCustomerWait[MAXN];	// 用户得到窗口前等待的时间
    int arrServe[MAXN];// 每个窗口客户等待时间之和
    
    void input(){
    	cin>>n>>s;
    	for(int i = 0;i < n;i ++){
    		cin>>arrCustomer[i];
    	}
    	memset(arrCustomerWait, 0, sizeof(arrCustomerWait));
        memset(arrServe, 0, sizeof(arrServe));
    }
    
    double caculate(){
    	int i,j = 0;
    	for(i = 0;i < n;i++){
    		arrCustomerWait[j] += arrCustomer[i];
    		arrServe[j] += arrCustomerWait[j];
    		j++;
    		if(j == s)
    			j = 0;
    	}
    	int answer = 0;
    	for(i = 0;i < s;i ++){
    		answer += arrServe[i];
    	}
    	return 1.0 * answer / n;
    } 
    
    int main(){
    	input(); 
    	sort(arrCustomer,arrCustomer + n);
    	printf("%.2f",caculate());
    	return 0;
    }
    
    
    展开全文
  • 关于最优服务次序问题与多处最优服务次序问题 1. 最优服务次序问题。 问题描述:设有n个顾客同时等待一项服务,顾客i需要的服务时间为ti,(1<=i<=n)。应如何安排n个顾客的服务次序才能使平均等待时间达到...

    关于最优服务次序问题与多处最优服务次序问题

    1. 最优服务次序问题。

    问题描述:设有n个顾客同时等待一项服务,顾客i需要的服务时间为ti,(1<=i<=n)。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?(平均等待时间是n个顾客等待服务时间总和除以n)

    输入:第一行为一个正整数n,表示有n个顾客

    第二行为n个正整数,表示n个顾客需要的服务时间

    输出:最小平均等待时间。

    源代码:

    #include <iostream>
    #include <algorithm>
    #include <iomanip>
    using namespace std;
    int main()
    {
     int n,i,sum1,sum2;
     double ave;
     sum1=0;
     sum2=0;
     double *a;
     cout<<"请输入顾客的数量n:";
     cin>>n;
     a = (double *)malloc(sizeof(double)*n);
     cout<<"每个顾客的需要服务的时间:"<<endl;
     for(i=0;i<n;i++)
      cin>>a[i];
     sort(a,a+n);
     for(i=0;i<n-1;i++)
     {
      sum1=sum1+a[i];
      sum2=sum2+sum1;
     }
     ave=sum2/n;
     cout<<setiosflags(ios::fixed)<<setprecision(2)<<"最小平均等待时间:"<<ave<<endl;
     return 0;
    }
    

    截图:
    1
    这里n=4,有4个顾客,第一个顾客应该为最小的数字2,他的等待时间为0;第二个应该为数字3,他的等待时间为2;以此类推,第三个顾客为数字4,等待时间为(2+3)=5;第三个顾客为数字5,等待时间为(2+3+4)=9。所以最小平均等待时间为(2+5+9)/4=4;

    2. 多处最优服务次序问题。

    问题描述:设有n个顾客同时等待一项服务,顾客i需要的服务时间为ti,(1<=i<=n)。共有s处可以提供此项服务。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?

    输入:第一行为两个正整数n和s

    第二行为n个正整数,表示n个顾客需要的服务时间

    输出:最小平均等待时间。

    源代码:

    #include <iostream>
    #include <algorithm>
    #include <iomanip>
    #include <cstdlib>
    using namespace std;
    void duo(double *a,double *b,int s,int n)
    {
     int i,j;
     double ave;
     double * c=new double[n];
     for(i=0;i<n;i++)
     {
      c[i]=0;
      b[i]=0;
     }
     i=0;
     j=0;
     while(i<n)
     {
      if(i<s)
      {
       c[j]=0;
       b[j]=0;
       i++;
       j++;
      }
      else
      {
       c[j]+=a[i-s];
       b[j]+=c[j];
       i++;
       j++;
      }
      if(j==s)
       j=0;
     }
     ave=0;
     for(i=0;i<s;i++)
      ave+=b[i];
     ave=ave/n;
     cout<<setiosflags(ios::fixed)<<setprecision(2)<<"最小平均等待时间:"<<ave<<endl;
    }
    int main()
    {
     int n,s,i;
     double ave;
     double *a,*b;
     cout<<"请输入n个顾客和s处可以提供此项服务:";
     cin>>n;
     cin>>s;
     a = (double *)malloc(sizeof(double)*n);
     b = (double *)malloc(sizeof(double)*n);
     cout<<"每个顾客的需要服务的时间:"<<endl;
     for(i=0;i<n;i++)
     {
      cin>>a[i];
      b[i]=0;
     }
     sort(a,a+n);
     /*for(i=0;i<n-1;i++)
     {
      sum1=sum1+a[i];
      sum2=sum2+sum1;
     }
     ave=sum2/n;*/
     duo(a,b,s,n);
     return 0;
    }

    截图:
    2

    展开全文
  • 实现4-6最优服务次序问题.cpp

空空如也

空空如也

1 2 3 4 5 ... 11
收藏数 203
精华内容 81
关键字:

最优服务次序问题